题解 | 最大子段和

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int []s = new int[a];
        long dp[] = new long[a];
        long m = 0;
        int i,j;
        for (i = 0; i < a; i++) {
            s[i] = in.nextInt();
        }
        dp[0] = s[0];
        m=s[0];
        for (j = 1; j < s.length; j++) {
            if(dp[j-1]<0){
                dp[j]=s[j]>s[j-1]?s[j]:s[j-1];
             m=m>dp[j]?m:dp[j];
            }else{
                dp[j]=dp[j-1]+s[j];
                m=m>dp[j]?m:dp[j];
            }
        }
        System.out.print(m);
    }
}

dp[j]:1到j的最大序列和

两种情况：

dp[j-1]>0,那么dp[j]=dp[j-1]+s[j]

dp[j-1]<0,那么dp[j]=s[j]；如果s[j]也<0,那么dp[j]=s[j]>s[j-1]?s[j]:s[j-1];

用m存储最大值