思路
比上一题（01-复杂度1 最大子列和问题），要多记录几个内容文章来源：https://www.toymoban.com/news/detail-586370.html
首尾元素，当前子序列开头元素，当前子序列结尾元素，最佳子序列开头元素，current是否在此处清零（则下一个元素是开头元素）文章来源地址https://www.toymoban.com/news/detail-586370.html
| 时间复杂度 | O(n) |
| 空间复杂度 | O(1) |
code(C++)
# include <iostream>
# include <algorithm>
int main(void)
{
long long ans = -1;
long long current = 0;
long long start, end, current_start;
bool expectNext = true;
int K;
std::cin >> K;
int firstNum, lastNum;
int k = K;
while (k--)
{
long long tmp;
std::cin >> tmp;
if (k == 0) lastNum = tmp;
if (k == K - 1) firstNum = tmp;
if (expectNext)
{
current_start = tmp;
expectNext = false;
}
current += tmp;
if (current < 0)
{
current = 0;
expectNext = true;
}
else if (current > ans)
{
ans = current;
start = current_start;
end = tmp;
}
}
if (ans >= 0)
std::cout << ans << " " << start << " " << end << std::endl;
else
std::cout << 0 << " " << firstNum << " " << lastNum << std::endl;
return 0;
}到了这里，关于01-复杂度2 Maximum Subsequence Sum的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
