最大化这个等式 E[a1]-E[a2]+E[a3]-E[a4]

Question

谁能帮我解决这个问题

我们必须最大化以下值： E[a1]- E[a2]+ E[a3]- E[a4] 其中 E 是一个数组约束： 1<=E<=100（尺码）

N>=4

a1>a2>a3>a4（指数）

输入格式

N（数组中整数的数量）

N 个值用空格分隔

输出

单个整数（最大值）

测试用例： I/P

6

3 9 10 1 30 40

O/P

46（40-1+10-3）（指数：5>3>2>0）

Answer 1

最好把这个问题分解，从小事做起。我们如何为 i > j 最大化 E[i]- E[j]？对于每个索引 i，我们可以跟踪数组 one_diff 中 i 之前的 E 中的最小值，其中 one_diff[i] = min(E[0], E[1], ... E[i-1])。然后，给定 i 的 E[i]- E[j] 的最大值只是 E[i] - one_diff[i].

对于三个术语，固定 i 的 E[i]- E[j] + E[k] 的最大值是 E[i] - min(E[j] - E[k]) over all j < i and k < j。这里的子问题实际上与上一个问题相同，除了我们现在想要给定 j 的 E[j]- E[k] 的最小值，因此将每个最大值更改为最小值。

对于四项，E[i]- E[j] + E[k] - E[l]的最大值需要E[j]- E[k] + E[l]的最小值，对于固定的j，变量k, l和l < k < j，所以进度与从两学期到三学期相同。

在 n 个变量的动态规划中，您应该首先尝试根据具有 n-1 个变量的子问题编写答案，然后解决该子问题。

Answer 2

#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;    
}

因为没人愿意回答所以我自己用dp

最大化这个等式 E[a1]-E[a2]+E[a3]-E[a4]

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

c++

recursion

dynamic

divide-and-conquer