牛客算法心得——环形数组的连续子数组最大和（dp）

大家好，我是晴天学长， 一个找连续子数组最大和的变形题，需要的小伙伴可以关注支持一下哦！后续会继续更新的。💪💪💪

1) .环形数组的连续子数组的最大和

描述
给定一个长度为 nn 的环形整数数组，请你求出该数组的 非空 连续子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。例如，对于数组 [1,3,-5,2,-4][1,3,?5,2,?4]而言，第一个数 11的前一个数是最后一个数 -4?4。
输入描述：
第一行输入一个正整数 nn ，代表数组的长度。
第二行为 nn 个整数 ai

输出描述：
输出一个整数，为原数组的非空子数组的最大可能和。
示例1
输入：
3
5 -3 5
输出：
10
说明：
从子数组 [5,5] 得到最大和 5 + 5 = 10
示例2
输入：
4
3 -2 2 -3
输出：
3
说明：
从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

2) .算法思路

• 两种情况（首位相连的）和首位不相连的
• 首尾相连的可以算最小的连续子数组得出，sum-就是。
• 注意整个数组都是最小的情况。

3）算法步骤

1.读取输入数据，包括环形数组的长度n和数组中的元素。
2.初始化变量sum为数组中所有元素的和。
3.创建两个数组dpmin和dpmax，用于记录以当前位置为结束点的最小和最大连续子数组的和。
4.初始化dpmin和dpmax的第一个元素为数组的第一个元素。
5.初始化变量max为dpmax的第一个元素，变量min为dpmin的第一个元素。
6.遍历数组，从第二个元素开始：
（1）更新dpmax[i]为当前元素nums[i]和nums[i]加上dpmax[i-1]的较大值。
（2）更新max为dpmax数组中的最大值。
7.遍历数组，从第二个元素开始：
（1）更新dpmin[i]为当前元素nums[i]和nums[i]加上dpmin[i-1]的较小值。
（2）更新min为dpmin数组中的最小值。
8.根据sum和min的比较结果，判断环形数组是否包含整个数组。
（1）如果sum等于min，则环形数组包含整个数组。将max作为结果。
（2）否则，用sum减去min的结果与max比较，取较大值作为结果。
9.输出结果。

4）. 代码实例

package NiukeTest.动态规划;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class 环形数组的连续子数组最大值 {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static String[] lines;

    public static void main(String[] args) throws IOException {
        lines = in.readLine().split(" ");
        int n = Integer.parseInt(lines[0]);
        int[] nums = new int[n];
        long sum = 0;
        lines = in.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(lines[i]);
            sum += nums[i];
        }
        // 两种情况（首位相连的）和首位不相连的
        // 首尾相连的可以算最小的连续子数组得出，sum-就是。
        int[] dpmin = new int[n];
        int[] dpmax = new int[n];
        dpmin[0] = nums[0];
        dpmax[0] = nums[0];
        long max = dpmax[0];
        long min = dpmin[0];
        for (int i = 1; i < n; i++) {
            dpmax[i] = Math.max(nums[i], nums[i] + dpmax[i - 1]);
            max = Math.max(max, dpmax[i]);
        }
        for (int i = 1; i < n; i++) {
            dpmin[i] = Math.min(nums[i], nums[i] + dpmin[i - 1]);
            min = Math.min(min, dpmin[i]);
        }
        long result;
        if (sum == min) {
            result = max;
        } else {
            result = Math.max(max, sum - min);
        }

        out.println(result);
        out.flush();
        out.close();
    }
}

5）. 总结

• 动规的状态分析很重要，开几个状态是关键。

试题链接：