题解 | 连续子数组最大和

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
        
        // 输入长度
        int n = Integer.parseInt(sc.nextLine());
        
        // 输入数组
        String[] arrStr = sc.nextLine().split(" ");
        int[] arr = new int[arrStr.length];
        for (int i = 0; i < arrStr.length; i++) {
            arr[i] = Integer.parseInt(arrStr[i]); // 修正：将字符串转换为整数
        }
        
        // 调用run方法计算结果
        long result = run(arr);
        
        // 输出结果
        System.out.println(result);
    }

    public static long run(int[] args) {
        int n = args.length;
        int[] dp = new int[n];
        
        // 初始化dp数组   这里也可以反过来，初始化dp最后一个然后往前遍历
        dp[0] = args[0]; // 第一个元素的最大和就是它本身
        
        // 动态规划计算最大和
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(args[i], dp[i - 1] + args[i]);
        }
        
        // 找到dp数组中的最大值
        long maxSum = dp[0];
        for (int i = 1; i < n; i++) {
            if (dp[i] > maxSum) {
                maxSum = dp[i];
            }
        }
        
        return maxSum;
}
}