题解 | #子数组最大连续和#

动态规划

import java.util.*;

public class Main {
    public static void main(String[] args){
         Scanner scan = new Scanner(System.in);
        while(scan.hasNext()){
            int len = scan.nextInt();
            long[] arr = new long[len];
            for (int i = 0; i < len; i++) {
                arr[i] = scan.nextInt();
            }
            //包含i在内的连续子数组最大和
            long[] dp = new long[len];
            dp[0] = arr[0];
            for (int i = 1; i < len; i++) {
                dp[i] = Math.max(arr[i], dp[i-1]+arr[i]);
            }
            Arrays.sort(dp);
            System.out.println(dp[len-1]);
        }
        
    }
}