连续子数组的元素之和最大值

一个整数数组，找出其中连续子数组的元素之和的最大值：
直接看代码，思路都在注释中。

public class FindMaxSubArraySum {

    public static void main(String[] args) {
        int[] arr = {-2, -3, 4, -1, -2, 1, 5, -3};
        System.out.println(maxSubArray(arr));
    }

    /**
     * 查找连续子数组元素和的最大值能保持复杂度为O(N)的关键在于，
     * 认识到这个子数组在含有正数的情况下，子数组的左右边界元素一定是正数
     * 只需一次循环就能遍历到那个子数组的元素和，然后保留这个值
     * 所以需要对负数的处理技巧，遍历求和时需要将负的值置为0，这样不论是全为负数还是含有正数，还是保留最大值就行
     * 全为正数的情况无需讨论。
     * @param nums int[]
     * @return int
     */
    public static int maxSubArray(int[] nums) {
        // 求最大值就应该用用最小值作为边界，而不是0，因为有很多小于0的整数
        int maxSum = Integer.MIN_VALUE;
        int maxTemp = 0;
        for (int num : nums) {
            maxTemp = maxTemp + num;
            // 保留最大值
            if (maxSum < maxTemp) {
                maxSum = maxTemp;
            }
            // 如果是负数，那么只需要保留最大值，后续无需再加上更小的负数
            if (maxTemp < 0) {
                maxTemp = 0;
            }
        }
        return maxSum;
    }
}

方法来源：
https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

至此，若有纰漏，望各位不吝赐教

• 还没有人评论，欢迎说说您的想法！

相关课程

英特尔® OpenVINO™工具套件初级课程

293074 0元 限免

基于 OpenVINO™ 的 AI 视觉应用进阶课

42050 0元 限免

基于 OpenVINO™ 的 AI 视觉应用基础课

56044 0元 限免