【摘要】题目
本题链接：连续最大和

一个数组有 N 个元素，求连续子数组的最大和。例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3。

输入描述：输出描述：示例1：解题思路：
本题是一个经典的动规问题。通过{6，-3，-2，7，-15，1，2，2}举例，dp[i]以数组下标为i的数作为结尾的子序列最大和，例如，dp[2]就是以-2结…

题目

本题链接：连续最大和

一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3。

输入描述：
在这里插入图片描述 输出描述：

示例1：

解题思路：

本题是一个经典的动规问题。通过{6，-3，-2，7，-15，1，2，2}举例，dp[i]以数组下标为i的数作为结尾的子序列最大和，例如，dp[2]就是以-2结尾的，子序列最大和的值为1（6 + -3 + -2），dp[3]就是以7结尾的，子序列最大和就是8（6 + -3 + -2 + 7）。当我们求dp[i]的时候可能会有两种情况，例如dp[3]，求出dp[2]是1，dp[2]+arr[3]是最大的，也有可能dp[2] + arr[3]小于当前的arr[3]，那此时最大就是arr[3]。

dp[i]就是dp[i – 1] + arr[i]与arr[i]作比较，选择较大的值。总结状态方程式：max(dp[i]) = GetMax(max(dp[i - 1]) + arr[i]， arr[i])。当i = 0 时，dp[0]就是arr[0]。

图解：
在这里插入图片描述

代码：

#include<iostream>
using namespace std;
#include<vector>

int GetMax(int a, int b)
{ return a > b ? a : b;
}

int main()
{ int n; cin >> n; vector<int> arr(n); for(int i = 0; i < n; i++) { cin >> arr[i]; } int sum = arr[0]; int max = arr[0]; for(int i = 1; i < n; i++) { //获取dp[i - 1] + arr[i]与arr[i]的较大值，子序列和最大值 sum = GetMax(sum + arr[i], arr[i]); if(sum > max) max = sum; } cout << max <<endl; return 0;
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32