Cod sursa(job #2847793)

Utilizator GeorgeAndreiGeorge Andrei Iarca GeorgeAndrei Data 11 februarie 2022 14:48:24
Problema Subsecventa de suma maxima Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
// 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;
}