#yyds干货盘点# 动态规划专题：连续子数组最大和

1.简述：

给定一个长度为 的数组，数组中的数为整数。

请你选择一个非空连续子数组，使该子数组所有数之和尽可能大，子数组最小长度为1。求这个最大值。

第一行为一个正整数 ，代表数组的长度。 

第二行为 个整数 ，用空格隔开，代表数组中的每一个数。 

连续子数组的最大之和。

输入：

8
1 -2 3 10 -4 7 2 -5

输出：

18

说明：

经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

输入：

1
2

输出：

2

输入：

1
-10

输出：

-10

2.代码实现：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 输入长度
        long n = Long.parseLong(sc.nextLine());
        // 输入数组
        String[] arrStr = sc.nextLine().split(" ");
        long[] arr = new long[arrStr.length];
        for (int i = 0; i < arrStr.length; i++) {
            arr[i] = Long.parseLong(arrStr[i]);
        }

        long run = run(arr.length, arr);
        System.out.println(run);
    }

    public static long run(int n, long[] arr) {
        if (arr == null || arr.length < 1) {
            return -1;
        }

        // 前一个元素下标对应最大的子数组和
        long cur = arr[0];
        // 总的最大子数组和
        long res = arr[0];
        for (int i = 1; i < arr.length; i ++) {
            // cur = 当前元素 和 当前元素 + 前一位元素下标对应最大子数组和 中的最大值
            cur = Math.max(arr[i], arr[i] + cur);
            // 更新 res
            res = Math.max(res, cur);
        }
        return res;
    }
}