Maximize this equation E[a1]-E[a2]+E[a3]-E[a4]

Question

Can anyone please help me how todo this problem

We have to maximize the value of: E[a1]- E[a2]+ E[a3]- E[a4] where E is an array constraints: 1<=E<=100 (size)

N>=4

a1>a2>a3>a4 (index)

Input format

N (no. of integers in array)

N value separated by spaces

Output

single integer(max value)

Test case: I/P

6

3 9 10 1 30 40

O/P

46 (40-1+10-3)(index: 5>3>2>0)

Answer 1

#include <bits/stdc++.h>

using namespace std;

int main()
{
int n;

cin>>n;

vector<int> v(n);

for(int i=0; i<n; i++) 

cin>>v[i];

vector<int> a1(n);

vector<int> a2(n);

vector<int> a3(n);

vector<int> a4(n);

int max4 = (-1)*v[0];

for(int i=0; i<n; i++)
{
    max4 = max(max4, (-1)*v[i]);
    a4[i] = max4;
}

int max3 = v[1]-v[0];
for(int i=1; i<n; i++)
{
    max3 = max(max3, v[i]+a4[i-1]);
    a3[i] = max3;
}

int max2 = (-1)*v[2]+v[1]-v[0];
for(int i=2; i<n; i++)
{
    max2 = max(max2, (-1)*v[i]+a3[i-1]);
    a2[i] = max2;
}

int max1 = v[3]-v[2]+v[1]-v[0];
for(int i=3; i<n; i++)
{
    max1 = max(max1, v[i]+a2[i-1]);
    a1[i] = max1;
}
cout<<a1[n-1]<<endl;
return 0;    
}

Since nobody cared to answer so I did on my own using dp