乐趣区

关于golang:Leetcode专题数组53最大子数组和

力扣连贯:https://leetcode-cn.com/probl…
解题思路:

  1. 看到题的第一眼,只有状态是须要动静决定的,那么大概率就是 DP 动静布局了
  2. 动静布局基本上是须要三架马车或者三板斧来决定的
    (1)确定数组元素的意义:即 dp[] 数组是什么含意
    (2)定义数组元素间的关系式,即状态转移方程:即 dp[n] = dp[n-1] + x
    (3)确定初始值:学过数学归纳法的都晓得,尽管咱们晓得了数组元素之间的关系式,如 dp[n] = dp[n-1] + dp[n-2], 然而咱们须要晓得最开始的值,dp[1] 和 dp[2]的值,这就是所谓的初始值

3. 回到这道题自身:(1)动静数组元素的意义 :dp[i](0 <= i <= n)示意在下标为 i 的时候,0~i 之间数组元素和的最大值(2) 状态转移方程 :dp[i] = dp[i – 1] + nums[i], 思考到数组中会有正数,那么方程进一步为:dp[i] = max(dp[i – 1] + nums[i], nums[i]) (3) 初始值:因为初始值必定是从数组第一个元素开始,所以初始值应该为数组第一个元素的值,那么求和就从第二个下标开始遍历

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
}
退出移动版