思路
动态规划题目,我们用 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; } } }