求所有子数组的和的最大值。要求时间复杂度为O(n)

时间:2022-05-25 17:14:51

题目:输入一个整形数组,数组里有正数也有负数,数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和,求所有子数组的和最大值。要求时间复杂度为O(n).

import java.util.ArrayList;

public class LargeSum {
public static void main(String args[]){
int s[]={1,-2,3,-10,-4,7,2,-5,6};
System.out.print(maxSubArraySum(s));
}
public static int maxSubArraySum(int []a){
int max=-(1<<31),i=0,sum=0;
ArrayList<Integer> ls=new ArrayList<Integer>();
while(i<a.length){
sum+=a[i++];
if(sum>max){
max=sum;
ls.add(a[i-1]);
}else if(sum<0){
sum=0;
ls.clear();
}else{
if(i-1<a.length-1){
if(a[i]+a[i-1]>0){
ls.add(a[i-1]);
}
}

}
}
for(int cc:ls){
System.out.print(cc+" ");
}
return max;
}
}