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

1.简述：

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

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

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

输入：

3
5 -3 5

输出：

10

说明：

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

输入：

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