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

1.简述：

描述

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

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

输入描述：

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

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

输出描述：

连续子数组的最大之和。

示例1

输入：

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

输出：

18

说明：

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

输入：

1
2

输出：

2

示例3

输入：

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;
}
}