题解 | 最大子段和

import java.util.Scanner;

import java.io.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int n = in.nextInt();
        int[] nums = new int[n + 1];
        //i结尾最大子数组和
        long[] dp = new long[n + 1];

        for (int i = 1; i <= n; i++) {
            nums[i] = in.nextInt();
        }
        dp[1] = nums[1];
        long ans = nums[1];
        for (int i = 2 ; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            if (dp[i] > ans) {
                ans = dp[i];
            }
        }
        out.println(ans);
        out.flush();
    }
}