Pagini recente » Cod sursa (job #2595363) | Cod sursa (job #1104499) | Cod sursa (job #2168634) | Cod sursa (job #1352805) | Cod sursa (job #2847781)
// 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());
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 + 2;
}
if (bestSubseq < best[i]) {
bestSubseq = best[i];
dr = i + 1;
}
}
}
// 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);
}
ssm();
cout << bestSubseq << st << dr;
return 0;
}