Maximum Sum of a Contiguous Subarray

1. Problem Description

HZ sometimes uses technical questions to confuse students outside computer science. After a testing-team meeting, he raised another problem: in classic one-dimensional pattern recognition, the maximum sum of a contiguous subvector is often needed. When all values are positive, the problem is easy. But if the vector contains negative values, should a negative value be included in the hope that nearby positive values compensate for it? For example, in {6,-3,-2,7,-15,1,2,2}, the maximum contiguous-subvector sum is 8 (from index 0 through index 3). Given an array, return the maximum sum of a contiguous subsequence. (The subvector length is at least 1.)

2. Approach

• Brute force
• Divide and conquer
• Dynamic programming
• Iterative trial: if the current sum plus the current number is smaller than the current number itself, restart the sum from the current number

3. Implementation

3.1. Brute Force

// Brute force
// Space: O(1)
// Time: 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. Divide and Conquer

// Time complexity: O(nlogn)
// Space complexity: 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. Dynamic Programming

// Dynamic programming: dp[i] = max(array[i], dp[i-1]+array[i])
// Time complexity: O(n)
// Space complexity: 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. Iterative Trial

• java

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

        // One variable records the maximum sum
        int maxSum = array[0];
        // Another variable records the current sum
        int currentSum = 0;
        for (int val : array)
        {
            currentSum += val;
            // If currentSum + currentValue < currentValue, restart the sum from the current value
            if (currentSum < val)
            {
                currentSum = val;
            }
            // If the current sum > the maximum sum, replace the maximum sum
            if (currentSum > maxSum)
            {
                maxSum = currentSum;
            }
        }

        return maxSum;
    }
}

• go

// Time complexity: O(n)
// Space complexity: 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. References

• Maximum Subarray Sum - NowCoder
• Sword Offer 42. Maximum Subarray Sum - LeetCode