# Editorial

Define `dp[i]`

to be the maximum Cypriot value of the subarray `a[i...]`

. Then, we can apply some choices for the first element.

- We can either allot a single cut to just this element.
- It can be merged with its neighbor.

If it is merged with its neighbor, then, of course, we want to maximise the Cypriot value of `a[i + 1 ...]`

before doing the merge. This is nothing but `dp[i]`

.

However, when we cut the first element alone, we can’t just blindly reuse the DP value of `a[i + 1 ...]`

because that DP maximizes

```
E1 = 1*s1 + 2*s2 + 3*s3 + ...
```

while we want to maximize

```
E2 = 2*s2 + 3*s3 + 4*s3
```

But notice that

```
E2 - E1 = suffix_sum
E2 = E1 + suffix_sum
```

Hence, to maximize E2, since the suffix sum is fixed, we can, in fact, use the maximized E1.

Hence, the DP transitions look like:

```
long long solve(vector<long long> &a) {
int n = a.size();
vector<long long> suffix_sum = a;
for (int i = n - 2; i >= 0; i--) {
suffix_sum[i] += suffix_sum[i + 1];
}
vector<long long> dp(n, 0);
// dp[i] is the answer for a[i ... ]
dp[n - 1] = a[n - 1];
for (int i = n - 2; i >= 0; i--) {
// Cut alone.
auto cut_alone = a[i] + dp[i + 1] + suffix_sum[i + 1];
// Cut with the group.
auto cut_with_group = a[i] + dp[i + 1];
dp[i] = max(cut_alone, cut_with_group);
}
return dp[0];
}
```

Notice that pseudocode above. At first glance, you can definitely say that it’s DP since we simulated both the choices and took the best one out of them. Now, let’s do a series of refactoring and code cleanup.

Since `dp[i] = max(cut_alone, cut_with_group)`

, we can replace it with `dp[i] = cut_alone`

if `cut_alone`

is bigger than `cut_with_group`

and vice-versa. When could `cut_alone`

be greater than `cut_with_group`

?

```
cut_alone > cut_with_group
a[i] + dp[i + 1] + suffix_sum[i + 1] > a[i] dp[i + 1]
suffix_sum[i + 1] > 0
```

Hence

```
dp[i] = a[i] + dp[i + 1]
dp[i] += suffix_sum[i + 1] if it is > 0
```

Now, try to read the statement above in english. You can say that you start with the last element with a running sum, and if the suffix sum is greater than 0, add it to the running sum. Also, notice that `cut_alone`

would be greater than `cut_with_group`

if suffix_sum is positive (as derived earlier). Hence, we even have an intuition that we should greedily cut the `i-th`

element alone if the suffix sum is positive.

So now, would you call this approach greedy or DP. Why or why not? Let me know on the comment thread