最大连续子序列
最大连续子序列
http://www.nowcoder.com/questionTerminal/afe7c043f0644f60af98a0fba61af8e7
思路
动态规划题目，我们用 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;
}
}
} 算法题解 文章被收录于专栏
不定期更新一些算法题解，有什么问题可以随时留言~
投递华为技术有限公司等公司10个岗位