最大连续子序列

思路

动态规划题目，我们用 dp[i] 表示以 nums[i] 结尾的连续子序列的最大元素和，则：

• dp[i] < 0，dp[i + 1] = nums[i + 1]
• dp[i] > 0，dp[i + 1] = dp[i] + nums[i + 1]

因为要输出首尾元素，其中尾部元素我们已经知道了，首部元素遍历一下就出来了，从 i 往前遍历到 dp[i] < 0。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
    int K;
    while(cin >> K && K){
        vector<int> nums(K, 0), dp(K, 0);
        int sum = -1, head = 0, tail = -1;
        for(int i = 0; i < K; i ++){
            cin >> nums[i];
            if(i > 0) 
                dp[i] = max(nums[i], nums[i] + dp[i - 1]);
            else dp[i] = nums[i];
            if(dp[i] > sum){
                sum = dp[i]; tail = i;
            }
        }
        // 所以 tail 没有改变，说明所有元素小于 0
        if(tail == -1) cout << 0 << " " << nums[0] << " " << nums.back() << endl;
        else {
            // 寻找首部元素
            for(int i = tail; i >= 0 ; i--){
                if(dp[i] < 0){
                    head = i + 1; break;
                }
            }
            cout << sum << " " << nums[head] << " " << nums[tail] << endl;
        }
    }
}