Pagini recente » Cod sursa (job #3141057) | Cod sursa (job #82119) | Cod sursa (job #472228) | Cod sursa (job #1405565) | Cod sursa (job #2847778)
// Subsecv de suma maxima
#include<iostream>
#include<fstream>
#include<vector>
#include<climits>
using namespace std;
vector<int> values;
int dr = 0, st = 0, bestSubseq = INT_MIN, maxVal = INT_MIN;
// void ssm() {
// vector<int> sum(values.size());
// sum[0] = values[0];
// for (int i = 1; i < values.size(); i++)
// sum[i] = sum[i - 1] + values[i];
// vector<int> best(values.size(), 0);
// int min = sum[0];
// for (int i = 1; i < values.size(); i++) {
// best[i] = sum[i] - min;
// if (min > sum[i]) {
// min = sum[i];
// st = i;
// }
// if (bestSubseq < best[i]) {
// bestSubseq = best[i];
// dr = i;
// }
// }
// }
void ssm2() {
vector<int> sum(values.size());
sum[0] = values[0];
maxVal = sum[0];
for (int i = 1; i < values.size(); i++) {
sum[i] = values[i] + sum[i - 1];
}
for (int i = 1; i < values.size(); i++) {
for (int j = 0; j < i; j++) {
if (sum[i] - sum[j] > maxVal) {
dr = i + 1; st = j + 2;
maxVal = sum[i] - sum[j];
}
}
}
}
int main() {
ifstream cin ("ssm.in");
ofstream cout ("ssm.out");
int n, x;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> x;
values.push_back(x);
}
ssm2();
cout << maxVal << st << dr;
return 0;
}