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

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int[] arr = new int[num];
        arr[0] = in.nextInt();
        
        int maxNum = arr[0];
        int minus = 0;
        for (int i = 1 ; i < num; i++) {
            arr[i] = in.nextInt();
            if(arr[i] < 0){
                minus++;
            }
            maxNum = Math.max(arr[i], maxNum);
            // System.out.println(arr[i] +"  " + maxNum +"  " + minus);
        }
        if(minus == num - 1 && arr[0] < 0) {
            System.out.println(maxNum);
            return;
        }
        if(num == 1){
            System.out.println(arr[0]);
            return;
        }
 
        int[] cost = new int[num];
        cost[0] = Math.max(0, arr[0]);
        int max = 0;
        for (int i = 1; i < num; i++) {
            cost[i] = Math.max(0, cost[i - 1] + arr[i]);
            max = Math.max(max, cost[i]);
            // System.out.println(cost[i - 1] + " " + cost[i]);
        }
        System.out.println(max);
    }
}