[DP] Maximum sum of subarray and modifications

max-sum-subarray.md

1. Let A is array, find maximum sum of subarray in A. Empty subarray is also valid.

int res = -1e9;
int dp0 = 0;
for (int i = 0; i < n; ++i) {
  dp0 = max(0, dp0 + A[i]);
  res = max(res, dp0);
}
return res;

The key observation, which allowed to simplify the code significantly, is that we don't we don't need to track the left side of the subarray. In this implementation we compute prefix sum dp0 and until this sum is greate than 0 it makes sense to consider it in maximization of the result. But as soon as it becomes 0, we can assume that we start from the next element so we nullify the prefix sum so it becomes actually a sum starting from the next element.

2. Now consider a more interesting problem, which is to find maximum sum of subarray in A if we can multiply any subarray with some value x.

int res = -1e9;
int dp0 = 0;
for (int i = 0; i < n; ++i) {
  dp0 = max(0, dp0 + A[i]);
  dp1 = max(dp0, dp1 + A[i]*x);
  dp2 = max(dp1, dp2 + A[i]);
  res = max(res, dp2);
}
return res;