编程题两道，都是关于动态规划的。
第一道，最大连续数组和。
要的是两段连续，且两段不能有重叠，求两个子段的最大和
（PS: 前面做题花了太多时间,最后慌慌张张的写了下第一题发现还剩10s, 点了下提交，发现报错了，哭了~)
例子：
输入：第一行测试用例数t，空一行后； 下一行第一个测试用例个数n；再下一行一个数组，空格隔开；再来行空；下一个用例
输入
3
10
1 -1 2 2 3 -3 4 -4 5 -5
5
-5 9 -5 11 20
10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
输出
13
40
-2
#include<bits/stdc++.h>
using namespace std;
int maxSum(vector<int>& data, int l, int r)
{
int sum = 0, b = 0;
for(int i = l; i<r+1; ++i)// 这里写成了 i=r
{
if(b>0) b += data[i];
else b = data[i];
sum = max(sum, b);
}
return sum;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<int> data(n);
for (int i = 0; i < n; ++i)
{
/* code */
cin>>data[i];
}
int ans = 0;
for (int i = 0; i < data.size(); ++i)
{
/* code */
int left = maxSum(data, 0, i);
int right = maxSum(data, i+1, data.size()-1); //这里写成data.size()了,给整越界了/
ans = max(ans, left+right);
}
cout<<ans;
}
return 0;
}
// 更新了代码 2020.8.17 秒了一眼，好像是背包问题，感觉短时间做不出来。
全部评论
(5) 回帖