Cod sursa(job #2978306)

Utilizator mati.coldea@gmail.comMatei Coldea [email protected] Data 13 februarie 2023 17:23:16
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("oo.in");
ofstream fout("oo.out");

int a[100005];
int dp[100005][3];// dp[i][0/1/2]= suma maxima stiind ca am la activ 0/1/2 luate

int main()
{
    int n;
    fin >> n;
    
    for (int i = 1; i <= n; i++) {
        fin >> a[i];
    }

    // am efect circular, deci pot avea si combinatii de (primul, ultimul)
    a[0] = a[n];
    a[n + 1] = a[1];

    int rez = -1;

    // am 3 pos:
    //-iau ultimul si primul element(start=0 si termin pe n-1)
    //-iau primul element fara ultimul(start=1)
    //-nu iau primul element(start=2 si voi termina pe n+1)
    // 
    // OBS:
    // la o pozitie, pot ori sa iau sau sa nu iau un element
    // si daca il iau, el poate fi primul sau al doilea element luat
    //

    for (int start = 0; start <= 2; start++) {
        dp[start][0] = 0;
        dp[start][1] = a[start];
        dp[start][2] = 0;
        for (int i = start+1; i <= n+start-1; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][1] + a[i];
            dp[i][1] = dp[i - 1][0] + a[i];

        }
        rez = max(dp[n + start - 1][0], rez);
    }

    fout << rez;

    return 0;
}