[数据结构与算法]【LeetCode】number 53: Maximum Subarray最大子序列

问题

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

解析

go解法：
1、动态规划
2、第一个元素的最大子序列和为其本身
3、第二个元素作为子序列最后一个数的时候，如果第二个元素加上第一个元素对应的最大的子序列的和大于第二个元素本身，则第二个元素对应的最大子序列的和就是它与第一个元素对应的最大的子序列的和的和，否则就是它自己本身
4、依次循环，根据前一个元素对应的最大子序列的和可以推导出后一个元素对应的最大子序列的

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