LeetCode 53 Maximum Subarray

一：题目地址

题目地址

二：解题思路

动态规划

三：代码

Java版本

public int maxSubArray(int[] nums) {
    int res = nums[0];
    int sum = 0;
    for (int num : nums) {
        // 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
        if (sum > 0) {
            sum = sum + num;
        } else {
            //sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
            sum = num;
        }
        res = Math.max(res, sum);
    }
    return res;
}

Go版本

func maxSubArray(nums []int) int {
    result := nums[0]
    sum := 0
    for _, num := range nums {
        if sum > 0 {
            sum = sum + num
        } else {
            sum = num
        }
        if sum > result {
            result = sum
        }
    }
    return result
}