DD1 连续最大和

DD1 连续最大和

连续最大和_牛客题霸_牛客网 (nowcoder.com)

---

// import java.util.*;
// public class Main {
//     public static void main(String[] args){
//         Scanner sc=new Scanner(System.in);
//         while(sc.hasNext()){
//             int n=sc.nextInt();
//             int[] array=new int[n];
//             for(int i=0;i<array.length;i++){
//                 array[i]=sc.nextInt();
//             }
//             int sum=array[0];
//             int max=array[0];
//             for(int i=1;i<array.length;i++){
//                 sum=Math.max(sum+array[i],array[i]);
//                 if(sum>max){
//                     max=sum;
//                 }
//             }
//             System.out.println(max);
//         }
//     }        
// }


import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            int[] array=new int[n];
            for(int i=0;i<array.length;i++){
                array[i]=sc.nextInt();
            }
            int[] dp=new int[n+1];
            dp[0]=array[0];
            int max=array[0];
            for(int i=1;i<array.length;i++){
                dp[i]=Math.max(dp[i-1]+array[i],array[i]);
                if(dp[i]>max){
                    max=dp[i];
                }
            }
            System.out.println(max);
        }
    }        
}