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

1.简述：

描述

给定一个长度为  的环形整数数组，请你求出该数组的 非空 连续子数组 的最大可能和 。环形数组 意味着数组的末端将会与开头相连呈环状。例如，对于数组 而言，第一个数 的前一个数是最后一个数 。

输入描述：

第一行输入一个正整数  ，代表数组的长度。第二行为  个整数 ，每个整数之间用空格隔开，代表数组的各个元素。

输出描述：

输出一个整数，为原数组的非空子数组的最大可能和。

示例1

输入：

3
5 -3 5

输出：

10

说明：

从子数组 [5,5] 得到最大和 5 + 5 = 10示例2

输入：

4
3 -2 2 -3

输出：

3

说明：

从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

2.代码实现：

import java.util.*;

public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
int[] dpMax = new int[n];
int[] dpMin = new int[n];
int sum = nums[0];
int maxVal = nums[0];
int minVal = nums[0];
dpMax[0] = nums[0];
dpMin[0] = nums[0];
for (int i = 1; i < n; i++) {
dpMax[i] = Math.max(dpMax[i - 1] + nums[i], nums[i]);
maxVal = Math.max(maxVal, dpMax[i]);
dpMin[i] = Math.min(dpMin[i - 1] + nums[i], nums[i]);
minVal = Math.min(minVal, dpMin[i]);
sum += nums[i];
}
if (maxVal > 0) System.out.println(Math.max(maxVal, sum - minVal));
else System.out.println(maxVal);
}
}