蓝桥杯算法提高VIP-和最大子序列 （Java代码）19行

解题思路:
这题是leetcode上面第53题，答案是看别人的，这中解法很巧妙，比如 1，2，3，4，-5，6，第一步先把1+2之和与2进行比较并且保存，再将其中较大者与1进行比较，得出最大值，再相当于用3替代1和2这两个数，3+3与3比较，较大者保存，并与3比比较。以此类推，直到1，2，3，4被10替代，10+（-5）=5，5与-5比较，较大者为5，5再和最大值10比较，10依旧是最大值，再相当于1，2，3，4，-5被他们的和5替代，5+6与6比较，5+6与10比较，得出最大值为11。

总结来说就是每次比较两个数的和与一个数，其实就是判断下面那个数是不是负数，不是负数，最大值为两个数之和，是负数，最大值为这个数，再把最大值与上一个最大值比较。
这题数据好像有点问题，不知道为什么ac不了


注意事项:





参考代码:

import java.util.Scanner;
public class 最大的子序列{

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int a[]=new int[n];
		for(int i=0;i<n;i++){
			a[i]=in.nextInt();
		}
		
		int maxSoFar=a[0], maxEndingHere=a[0];
		for (int i=1;i<a.length;++i){
		    maxEndingHere= Math.max(maxEndingHere+a[i],a[i]);
		    maxSoFar=Math.max(maxSoFar, maxEndingHere);	
		    }
		    System.out.println(maxSoFar);
	}
	}