Hints

Recall that in Yet Another Monster Fight, instead of worrying above the original problem, we focused on what happens when the lightning strike starts at the i-th monsert. On similar lines, instead of solving the problem for the entire array, let’s solve it for the subarray that starts at i.

Formally, define dp[i] to be the maximum Cypriot value of the subarray starting at i (and ending at the last index). The answer to the original problem would then be dp[0].

How do you populate this DP?

You might try guessing how long the first cut would be, and then wondering how to compute the answer from the remaining dp[i], i.e. try the first cut (for the leftmost subarray) of length 1, 2, 3, … n and take the best out of them.

However, there’s a much simpler transition. Think about the technique used in Clear the String.

Instead of thinking about the first cut, think small. Think about what happens to the first element. Either it will be cut alone in a single subarray, or it’d be part of it’s neighbor’s cut. Can you figure out the DP transitions now?

If the i-th element is cut alone, it means that the first subarray is of size 1, adding a contribution of 1*a[i]. Now, we need to maximize 2*s1 + 3*s3 + ...

But we do know dp[i + 1] which is the maximum value for 1*s1 + 2*s2 + 3*s3 + ... . Hence, this diverts our attention on how these 2 equations are related:

E1 = 1*s1 + 2*s2 + 3*s3 ....
E2 = 2*s1 + 3*s3 + 4*s4 ....

It’s easy to see that

E2 - E1 = s1 + s2 + s3 + ....
E2 = E1 + sum[i + 1, ....]

Hence, if we want to maximize 2*s1 + 3*s3 + ..., then we should in fact maximize Cypriot value of dp[i + 1] and add the suffix sum.

Now, if the i-th element is not cut alone, then it is part of the first group. Hence, it would only contribute 1*a[i] while dp[i] will have the remaining contribution.

cut_with_group = a[i] + dp[i + 1]
cut_alone = a[i] + dp[i + 1] + suffix_sum[i + 1]

Hence, if we fill this DP array from right to left, we have an O(n) solution.

See the editorial for a discussion about Greedy vs DP.