53. 最大子数组和

53. 最大子数组和

一，描述

难度：中等

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

子数组是数组中的一个连续部分。

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

二，思路：

方法一（动态规划）：

1. 使用原nums数组充当动态规划数组。
2. 动态规划数组的nums[i]代表当前（0-i）之间最大连续子数组的值。
3. 状态转移方程nums[i] = max(nums[i-1]+nums[i]，nums[i])。

方法二（不亏本法）：

1. 使用 0起始本钱，小于0从头再来，大于0继续开始，每一次旅途计算总金额。
2. 从头遍历链表，一轮遍历完毕后，留下的最大的值就是最大的值。

三，代码

方法一：

func maxSubArray(nums []int) int {
    res := -10000;
    sum := 0;
    // 0起始本钱，小于0从头再来，大于0继续开始，每一次旅途计算总金额
    for i:=0;i<len(nums);i++{
        sum += nums[i];
        res = max(res,sum);
        if(sum < 0){
            sum =0;
        }
    }
    return res;
}

方法二：

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;
}

反思 ：有点像人生
走完这一生
如果我和你在一起会变得更好，那我们就在一起，否则我就丢下你。
我回顾我最光辉的时刻就是和不同人在一起，变得更好的最长连续时刻