Cod sursa(job #2791332)

Utilizator paul911234vaida paul paul911234 Data 30 octombrie 2021 13:04:07
Problema Subsecventa de suma maxima Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
using namespace std;

const int SIZE_N = 6000001;

int sp[SIZE_N] = {0};

/*int brute_force(int index,int n, int &begin, int &end) {
    if (n > 1) {
      if (index == n) {
           brute_force(index = 1,n - 1, begin, end);
      } else {
          if (brute_force(index + 1, n, begin, end) > sp[n] - sp[index]) {
              begin = index + 1;
              end = n;
          }
      }
    }
}*/
int main() {
    int x, n;
    cin >> n >> x;
    sp[1] = x;
    for (int i = 2; i <= n; ++i) {
        cin >> x;
        sp[i] = sp[i - 1] + x;
    }
    int maxim = sp[n - 1] - sp[1], begin, end;
    for (int i = n; i >= 1; --i) {
         for (int j = 1; j < n; ++j) {
              if (maxim < sp[i] - sp[j]) {
                  maxim = sp[i] - sp[j - 1];
                  begin = j;
                  end = i;
              }
         }
    }
    cout << maxim << ' ' << begin << ' ' << end;
  }