连续子数组的最大和

1. 题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

2. 思路

• 暴力法
• 分治
• 动态规划
• 试探：如果当前和+当前数<当前数，那么不如从当前数开始继续求和

3. 实现

3.1. 暴力法

//暴力法
//空间：O(1)
//时间：O(N²)
func FindGreatestSumOfSubArray(array []int) int {
	if len(array) == 0 {
		return 0
	}

	max := array[0]
	for i := 0; i < len(array); i++ {
		currentSum := array[i]
		if currentSum > max {
			max = currentSum
		}
		for j := i + 1; j < len(array); j++ {
			currentSum += array[j]
			if currentSum > max {
				max = currentSum
			}
		}
	}

	return max
}

3.2. 分治

//时间复杂度：O(nlogn)
//空间复杂度：O(logn)
func FindGreatestSumOfSubArray4(array []int) int {
	if len(array) == 0 {
		return 0
	}

	return findGreatestSumOfSubArray4(array, 0, len(array)-1)
}

func findGreatestSumOfSubArray4(array []int, begin int, end int) int {
	if end-begin <= 1 {
		return max(array[begin],array[end])
	}

	mid := begin + (end-begin)>>1

	leftMax := array[mid-1]
	leftSum := 0
	for i := mid - 1; i >= begin; i-- {
		leftSum += array[i]
		leftMax = max(leftSum, leftMax)
	}

	rightMax := array[mid]
	rightSum := 0
	for i := mid; i <= end; i++ {
		rightSum += array[i]
		rightMax = max(rightSum, rightMax)
	}
	return max(leftMax+rightMax, findGreatestSumOfSubArray4(array, begin, mid), findGreatestSumOfSubArray4(array, mid, end))
}

func max(data ...int) int {
	max := data[0]
	for i := 1; i < len(data); i++ {
		if data[i] > max {
			max = data[i]
		}
	}
	return max
}

3.3. 动态规划

//动态规划：dp[i] = max(array[i], dp[i-1]+array[i])
//时间复杂度：O(n)
//空间复杂度：O(n)
func FindGreatestSumOfSubArray2(array []int) int {
	if len(array) == 0 {
		return 0
	}

	dp := make([]int, len(array)+1)
	dp[0] = 0
	ret := array[0]
	for i := 1; i <= len(array); i++ {
		dp[i] = Max(array[i-1], dp[i-1]+array[i-1])
		ret = Max(ret, dp[i])
	}
	return ret
}
func Max(a int, b int) int {
	if a < b {
		return b
	}
	return a
}

3.4. 试探

• java

public class 连续子数组的最大和
{
    public int FindGreatestSumOfSubArray(int[] array)
    {
        //检查参数
        if (array == null || array.length == 0)
        {
            return 0;
        }

        //一个变量记录最大和
        int maxSum = array[0];
        //另一个变量记录当前和
        int currentSum = 0;
        for (int val : array)
        {
            currentSum += val;
            //如果当前和+当前数<当前数，那么不如从当前数开始继续求和
            if (currentSum < val)
            {
                currentSum = val;
            }
            //如果当前和>最大和，替换最大和
            if (currentSum > maxSum)
            {
                maxSum = currentSum;
            }
        }

        return maxSum;
    }
}

• go

//时间复杂度：O(n)
//空间复杂度：O(1)
func FindGreatestSumOfSubArray3(array []int) int {
	if len(array) == 0 {
		return 0
	}

	max := array[0]
	currentSum := 0
	for i := 0; i < len(array); i++ {
		currentSum += array[i]
		if currentSum < array[i] {
			currentSum = array[i]
		}
		if currentSum > max {
			max = currentSum
		}
	}
	return max
}

func maxSubArray(nums []int) int {
    if len(nums) == 0 {return 0}
    maxSum := nums[0]
    currentSum := 0
    for _, num := range nums {
        currentSum = max(currentSum+num, num)
        maxSum = max(maxSum, currentSum)
    }
    return maxSum
}

func max(a, b int) int {
    if a > b {return a}
    return b
}

4. 参考

• 连续子数组的最大和_牛客题霸_牛客网
• 剑指 Offer 42. 连续子数组的最大和 - 力扣（LeetCode）