原题传送门

1. 问题描述

2. Solution

1、思路分析
DP求最大连续子序列和，设输入数组为nums。(参考算法笔记11.2 最大连续子序列和)
1> 状态定义: dp[i] = 以nums[i]结尾的最大连续子序列和。
2> 状态转移方程:
case 1: 以nums[i]结尾的最大和的连续序列只有一个元素，即nums[i]。
case 2: 最大和为dp[i-1]+nums[i]。
整合上面两种情况，得到转态转移方程: dp[i] = max{nums[i], dp[i-1]+nums[i]}
用sumOfHere替代dp[i-1]，res替代dp[i]以降低空间复杂度。
3> 边界: dp[0] = nums[0]。

2、代码实现

// PAT Advance Level 1007 // Ye Qiu #include <iostream> #include <cstdio> #include <vector>  using namespace std;  int main() { #ifdef ONLINE_JUDGE #else     freopen(input/1007.txt, r, stdin); #endif     int k, sumOfHere = 0, res = -1, begin = 0, start = 0;     scanf(%d, &k);     int end = k - 1;     vector<int> nums(k);     for (int i = 0; i < k; i++) {         cin >> nums[i];         sumOfHere += nums[i];         if (sumOfHere < 0) {             sumOfHere = 0;             begin = i + 1;         } else if (sumOfHere > res) {             res = sumOfHere;             start = begin;             end = i;         }     }     if (res < 0) res = 0;     printf(%d %d %d, res, nums[start], nums[end]);     return 0; } 

3、复杂度分析
时间复杂度: O(n)
空间复杂度: O(n)