Cod sursa(job #2978301)

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

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

int a[100005];

int main()
{
    int n;
    fin >> n;
    

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


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




    //iau primul element
    dp[1][0] = 0;
    dp[1][1] = a[1];
    dp[1][2] = 0;

    for(int i = 2; i <= n; 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];

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




    // iau si primul si ultimul element
    int dp2[100005][3];


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

   // cout << dp2[1][2];
    

    rez = max(rez, dp2[n - 1][0]);


    // nu iau primul elemenr
    int dp1[100005][3];

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

    rez = max(rez, dp1[n + 1][0]);
    fout << rez;

    
   // cout << dp[n][0];








    return 0;
}