题解 | #环形牛群的最小和#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int minSubarraySum(int[] nums) {
        int minSum = nums[0];
        int sum = 0;
        for (int num : nums) {
            minSum = Math.min(minSum, minSum + num);
            sum += num;
        }
        // 如果全部是正数
        if (minSum > 0) {
            return minSum;
        }
        return Math.min(calMinSum(nums), sum - calMaxSum(nums));
    }

    public int calMaxSum(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int tempMax = nums[0];
        for (int i = 1; i < nums.length; i++) {
            tempMax = Math.max(nums[i], nums[i] + tempMax);
            maxSum = Math.max(maxSum, tempMax);
        }
        return maxSum;
    }

    public int calMinSum(int[] nums) {
        int minSum = Integer.MAX_VALUE;
        int tempMin = nums[0];
        for (int i = 1; i < nums.length; i++) {
            tempMin = Math.min(nums[i], tempMin + nums[i]);
            minSum = Math.min(tempMin, minSum);
        }
        return minSum;
    }
}

本题知识点分析：

1.动态规划

2.API函数(Math.min和Math.max)

3.数学模拟

4.数组遍历

本题解题思路分析：

1.先计算连续子数组的最小和，不考虑环形，然后如果minValue>0，说明全部是正数，所以直接返回minValue

2.如果有负数，那么就先计算连续子数组（不考虑环形数组）的最小和，然后求连续子数组（不考虑环形）的最大和

3.返回 连续子数组（不考虑环形数组）的最小和 与 总和-最大和 的较小值

本题使用编程语言: Java

如果你觉得本篇文章对你有帮助的话，可以点个赞支持一下，感谢~