子数组最大累加和

题目(LeetCode #53)

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解法

创建两个变量, current 和 maxSum , 遍历数组, 将每个元素累加到 current 上, 再与 maxSum 比较, 使 maxSum 总保存 current 的最大值, 若累加过程中 current 变为负数, 则手动将其归零, 继续计算.

Java

public class MaxSumOfSubarray {
    public static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int current = 0;
        int maxSum = Integer.MIN_VALUE;

        for (int num : nums) {
            current += num;
            maxSum = Math.max(current, maxSum);
            current = Math.max(current, 0);
        }

        return maxSum;
    }
}

Python

class MaxSumOfSubarray:
    def maxSubArray(self, nums):
        if not nums or len(nums) == 0:
            return 0

        current = 0
        max_sum = float("-inf")

        for num in nums:
            current += num
            max_sum = max(current, max_sum)
            current = max(0, current)

        return max_sum

Go

Go 中整型常量可定义如下

const INT_MAX = int(^uint(0) >> 1) 	// 有符号最大值
const INT_MIN = ^INT_MAX			// 有符号最小值

const UINT_MIN uint = 0				// 无符号最小值, 即为 0
const UINT_MAX = ^uint(0)			// 无符号最大值

func maxSubArray(nums []int) int {
	if nums == nil || len(nums) == 0 {
		return 0
	}

	current := 0
	maxSum := ^int(^uint(0) >> 1)

	for _, num := range nums {
		current += num
		maxSum = max(current, maxSum)
		current = max(0, current)
	}

	return maxSum
}

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

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}