题解 | 连续子数组最大和(ACM版本)

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        
        int[] nums = new int[n];
        int index = 0;
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            nums[index] = a;
            index++;
        }
        if(n == 1){
            System.out.println(nums[0]);
            return;
        }
        // 存储到n位置的连续子数组最大和
        int[] dp = new int[n];
        dp[0] = nums[0];
        /**
            dp[i] = Math.max()
         */
        // 总的最大子数和
        int res = dp[0];
        // 对于某一个元素，该位置上大的子数组和 = max（该元素的值， 该元素的值 + 前一个位置对应的最大子数组和），因为 前一个位置对应的最大子数组和 可能为负数，如果为负数，那么之前的就应该舍弃掉，以当前元素为新的最大子数组和。
        for(int i = 1; i < n; i++){
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            // 因为不同大小的子数组的最大连续子数和不一样，所以需要用res来固定最大的那个
            res = Math.max(res, dp[i]);
        }
        System.out.println(res);
    }
}