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

对于这个问题 思路是 考虑每个数作为结尾的情况的最大连续子数组和

比较当前数加上前面最大的连续子数组和与当前数自己作为新的子数组和的开头谁大

preSum 是用来记录当前下标前一个的最大连续子数组和

如果arr[i] > arr[i]+preSum 说明 preSum带来的是负作用 我们舍弃它 只用arr[i] 作为新开头

反之，说明preSum带来的是正作用 我们就更新preSum

在这个同时 我们维护一个全局变量ans 记录答案

最后返回ans

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int ans = Integer.MIN_VALUE;
        int preSum = 0;
        for(int i = 0;i<n;i++){
            preSum = Math.max(arr[i],arr[i]+preSum);
            ans = Math.max(ans,preSum);
        }
        System.out.println(ans);
    }
}