题解 | 最大子段和

动态规划

dp[i]:数组中第i个元素a[i]结尾的连续子数组的最大和

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[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=in.nextInt();
        }
        
        
        long[] dp=new long[n];//数组中第i个元素a[i]结尾的连续子数组的最大和
        long res=a[0];
        dp[0]=a[0];
        for(int i=1;i<n;i++){
            dp[i]=Math.max(dp[i-1]+a[i],a[i]);
            res=Math.max(res,dp[i]);

        }
        System.out.println(res);
    }
}