2013-12-05 15:47:00Morris
[UVA][Easy] 12650 - Dangerous Dive
SampleInput
5 3
3 1 5
6 6
6 1 3 2 5 4
SampleOutput
2 4
*
連續最大和問題 O(n)
#include <sstream>
#include <stdio.h>
#include <algorithm>
using namespace std;
char s[1048576];
int main() {
while(gets(s)) {
stringstream sin(s);
int ret = 0, sum = 0, x;
while(sin >> x) {
sum += x;
if(sum < 0) sum = 0;
ret = max(ret, sum);
}
printf("%d\n", ret);
}
return 0;
}
5 3
3 1 5
6 6
6 1 3 2 5 4
SampleOutput
2 4
*
連續最大和問題 O(n)
#include <sstream>
#include <stdio.h>
#include <algorithm>
using namespace std;
char s[1048576];
int main() {
while(gets(s)) {
stringstream sin(s);
int ret = 0, sum = 0, x;
while(sin >> x) {
sum += x;
if(sum < 0) sum = 0;
ret = max(ret, sum);
}
printf("%d\n", ret);
}
return 0;
}