leetcode53 最大子序列和 动态规划

最大子序和

给定一个数组,有正有负,求最大子数组和

[-2,1,-3,4,-1,2,1,-5,4]
连续子数组 [4,-1,2,1] 的和最大，为 6

状态表示:

​ $dp\left[i\right]表示第i个数字位置能得到的最大和$dp[i]表示第i个数字位置能得到的最大和

转移方程:

$dp\left[i\right]=max\left(dp\right[i-1]+num[i],a[i\left]\right)$dp[i]=max(dp[i−1]+num[i], a[i])

从前面的最优子数组转移过来,或者只要当前位置

初始状态:

​ $第一个数字最大和就是自己:dp\left[0\right]=num\left[0\right]$第一个数字最大和就是自己:dp[0]=num[0]

int maxSubArray(vector<int>& a) {
  int n = a.size();
  //dp[i] = max(a[i-1], dp[i-1]+a[i]) 转移方程
  vector<int> dp(n, 0);
  dp[0] = a[0];
  int ans = dp[0];
  for(int i=1; i<n; i++) {
    dp[i] = max(dp[i-1]+a[i], a[i]);
    ans = max(dp[i], ans);
  }
  return ans;
}