1
最大子数组和
source link: https://helloteemo.github.io/2022/11/17/leetcode/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/%E6%9C%80%E5%A4%A7%E5%AD%90%E6%95%B0%E7%BB%84%E5%92%8C/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
本文最后更新于：2022年11月17日 中午
最大子数组和
题目：点我直达
// maxSubArray 最大子数组和
// 这里采用动态规划思路求解
// 定义 dp[i] 为第i个元素的包含前n个子数组的最大值
// 如果 dp[i-1] 为负数的话，就会对当前的dp[i]最大值起到副作用
// 所以我们直接拿arr[i]作为当前dp[i]的最大值即可
// 如果 dp[i-1] 为正数的话，我们直接拿当前的arr[i]加上就是dp[i].因为arr[i]是必须的
// 故不论 arr[i] 是正数还是负数都会产生正作用
// 其中 dp[0] 直接拿 arr[0] 即可
// 动态方程式为:
// arr[i] dp[i-1]<=0
// dp[i] =
// arr[i] + dp[i-1] dp[i-1]>0
func maxSubArray(nums []int) int {
// 定义dp
var dp = make([]int, len(nums))
// dp[0] 没法按照下面的公式求解
dp[0] = nums[0]
for i, num:= range nums{
if i == 0{
continue
}
// 下面就是转移方程式
if dp[i-1] <=0 {
dp[i] = num
}else{
dp[i] = num + dp[i-1]
}
}
// 拿到最大值返回即可
var m = dp[0]
for _, d := range dp {
m = max(d,m)
}
return m
}
func max(a,b int) int{
if a>=b {
return a
}
return b
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK