疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

求连续子数组最大和,两种算法


 

  一个整形数组,数组里有正数也有负数。

  数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和,求所有子数组的和的最大值

  下面是一个效率很低的方法两层循环,思路是分别以每一个元素为起点,定义一个temp值保存现有的最大和,如果遍历到的连续子数组的和大于temp那么则交换两者的值。

  [java]

  import java.util.*;

  class BigChild

  {

  public static void main(String[] args)

  {

  int temp=0;

  Scanner sc=new Scanner(System.in);

  String str=sc.nextLine();

  String[] st=str.split(",");

  int[] arr=new int[st.length];

  for(int i=0;i

  {

  arr[i]=new Integer(st[i]);

  }

  for(int i=0;i

  {

  //sum一定要在这里定义,否则会变成一个累加值

  int sum=0;

  for(int j=i;j

  {

  sum+=arr[j];

  if(sum>temp)

  temp=sum;

  }

  }

  System.out.println(temp);

  }

  }

  import java.util.*;

  class BigChild

  {

  public static void main(String[] args)

  {

  int temp=0;

  Scanner sc=new Scanner(System.in);

  String str=sc.nextLine();

  String[] st=str.split(",");

  int[] arr=new int[st.length];

  for(int i=0;i

  {

  arr[i]=new Integer(st[i]);

  }

  for(int i=0;i

  {

  //sum一定要在这里定义,否则会变成一个累加值

  int sum=0;

  for(int j=i;j

  {

  sum+=arr[j];

  if(sum>temp)

  temp=sum;

  }

  }

  System.out.println(temp);

  }

  }

  下面是一个只有一层循环的算法

  思路是当前面的几个数,加起来后,temp<0后, 把temp重新赋值,置为下一个元素,temp=a[i]。当temp>sum,则更新sum=temp; 若temp

  [java]

  import java.util.*;

  class BigChild

  {

  public static void main(String[] args)

  {

  int temp=0;

  int sum=0;

  Scanner sc=new Scanner(System.in);

  String str=sc.nextLine();

  String[] st=str.split(",");

  int[] arr=new int[st.length];

  for(int i=0;i

  {

  arr[i]=new Integer(st[i]);

  }

  for(int i=0;i

  {

  if(temp<0)

  temp=arr[i];

  else

  temp+=arr[i];

  if(temp>sum)

  sum=temp;

  }

  System.out.println(sum);

  }

  }

  import java.util.*;

  class BigChild

  {

  public static void main(String[] args)

  {

  int temp=0;

  int sum=0;

  Scanner sc=new Scanner(System.in);

  String str=sc.nextLine();

  String[] st=str.split(",");

  int[] arr=new int[st.length];

  for(int i=0;i

  {

  arr[i]=new Integer(st[i]);

  }

  for(int i=0;i

  {

  if(temp<0)

  temp=arr[i];

  else

  temp+=arr[i];

  if(temp>sum)

  sum=temp;

  }

  System.out.println(sum);

  }

  }