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

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

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

下面是一个效率很低的方法两层循环，思路是分别以每一个元素为起点，定义一个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);
}
}