1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <vector>
using namespace std;
long helper(vector<vector<long>>& dp, int p, int deg, vector<int>& array) {
if(deg == -1) return 0;
if(p == array.size()) return INT_MIN;
if(dp[p][deg] != INT_MIN) return dp[p][deg];
int n = array.size();
for(int i = p + 1; i <= n; i++) {
dp[p][deg] = max(dp[p][deg], helper(dp, i, deg - 1, array));
}
if(deg & 1) dp[p][deg] += array[p];
else dp[p][deg] -= array[p];
return dp[p][deg];
}
int maximizeExpression(vector<int> array) {
if(array.size() < 4) return 0;
long n = array.size();
vector<vector<long>> dp(n, vector<long>(4, INT_MIN));
long res = INT_MIN;
for(int i = 0; i < n; i++) {
res = max(res, helper(dp, i, 3, array));
}
return res;
}
|
