ブラシ問題08-連続するサブシーケンスの最大和を求めます

        （        ），         （       ）    。        O(n)。

【  】         N（N>=1）

   N ，     ，     N   

  ：
8
1
-2
3
10
-4
7
2
-5
  ：
18

       3, 10, -4, 7, 2

import java.util.Scanner;
/**
*       @SteveNolan    
*/
public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		
		int max = a[0],sum = 0;
        for(int i = 0;i < n;i++){
            sum += a[i];        
            if(sum > max)
                max = sum;
            //sum          ，        ，       0
            //        ，  a[i]             
            if(sum < 0){
                sum = 0;
            }
        }
        System.out.println(max);
	}
}