Cod sursa(job #2847778)

Utilizator GeorgeAndreiGeorge Andrei Iarca GeorgeAndrei Data 11 februarie 2022 14:23:06
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(), 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;
}