Max Sum Subarray After K Modifications

Do not invent the operation

“After K modifications” is ambiguous: a modification might multiply an element, replace it, negate it, or change one contiguous segment. First ask for the exact operation, whether up to or exactly k changes are required, and whether the chosen subarray must be nonempty. Then state a DP such as dp[i][j]: best sum of a subarray ending at index i after using j modifications. Each transition compares starting at i with extending the previous state, plus the unmodified or modified contribution mandated by the actual rule.

Explain the invariant

The ending-at-i restriction makes every transition local; a separate answer tracks the best state over all endpoints and permitted j. Initialize impossible states to negative infinity so an illegal number of modifications is never selected, and take care with overflow when the operation can magnify values. The typical formulation is O(nk) time and O(k) space with rolling rows, but the exact transition and Big-O must follow the clarified operation. Naming the ambiguity is better than confidently solving a different problem.