Bela Jornada

A BR-101 (Também chamada de Translitorânea, oficialmente nomeada Rodovia Governador Mário Covas) é uma estrada longitudinal do Brasil. É a mais longa do país.

A estrada tem N checkpoints. Cada checkpoint tem um valor de beleza denotado como um array A em ordem do ínício da estrada até o final da mesma. O valor de beleza de um checkpoint consiste na beleza dos lugares próximos ao checkpoint. Você está planejando viajar pela estrada. Como é uma longa estrada, você irá parar em um dos checkpoints para um pouco de descanso e após este descanso, contiuar sua jornada.

Então, sua jornada em dois sub-arrays próximos, $S_1$ sendo os checkpoints antes de seu descanso (incluindo o que você irá parar) e $S_2$ sendo os checkpoints depois de seu descanso, tal que $tamanho(S_1)+tamanho(S_2)=N$ (i.e. todo checkpoint pertence a um exato sub-array).

A beleza total da jornada é definida por $soma(S_1)\ast soma(S_2)$ onde $soma(S)$ é a soma total do valor de beleza no sub-array S. Você quer maximizar o valor de $soma(S_1)\ast soma(S_2)$.

Example:

Input:  n = 5, a = {1, 2, 3, 4, 5}
Output: 54

Approach

C++

#include <bits/stdc++.h>
using namespace std;

long long belaJordana(long long n, long long a[])
{
    long long left[n + 1], right[n + 1];
    left[0] = 0;
    right[n] = 0;
    for (long long i = 1; i <= n; i++)
        left[i] = left[i - 1] + a[i - 1];
    for (long long i = n - 1; i >= 0; i--)
        right[i] = right[i + 1] + a[i];
    long long max1 = 0;
    for (long long i = 1; i < n; i++)
        max1 = max(max1, left[i] * right[i]);
    return max1;
}
int main()
{
    long long n = 5;

    long long a[n] = {1, 2, 3, 4, 5};

    cout << belaJordana(n, a) << "\n";

    return 0;
}