Maximize this equation E[a1]-E[a2] E[a3]-E[a4] [closed]-CodePudding

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

3 9 10 1 30 40

O/P

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

CodePudding user response：

It's best to break this problem down, and start with smaller cases. How would we maximize E[i]- E[j] for i > j? We could track, for every index i, the minimum value in E before i in an array one_diff where one_diff[i] = min(E[0], E[1], ... E[i-1]). Then, the max of E[i]- E[j] for a given i is just E[i] - one_diff[i].

For three terms, the max of E[i]- E[j] E[k] for a fixed i is E[i] - min(E[j] - E[k]) over all j < i and k < j. The subproblem here is actually the same as the last problem, except we now want the min of E[j]- E[k] for a given j, so change every max to a min.

For four terms, the max of E[i]- E[j] E[k] - E[l] requires the min of E[j]- E[k] E[l] for a fixed j, and variable k, l with l < k < j, so the progression is the same as going from two to three terms.

In dynamic programming over n variables, you should first try writing the answer in terms of a subproblem with n-1 variables, then solve that subproblem.

CodePudding user response：

#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