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