Maximum Subarray Sum After Multiplier - Video Solutions

Problem Overview: You are given an array and a multiplier. You may choose one contiguous subarray and multiply every element in that subarray by the multiplier exactly once. After the operation, compute the maximum possible subarray sum. The challenge is deciding where applying the multiplier increases the best possible sum.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

Try every possible subarray [l, r] as the segment to multiply. For each choice, create the modified array where elements in [l, r] are multiplied by the factor. Run a standard maximum subarray calculation such as Kadane’s algorithm to compute the best subarray sum of the modified array. There are O(n^2) choices for [l, r], and each evaluation takes O(n), giving O(n^3) time. This method is straightforward but impractical for large inputs.

Approach 2: Prefix-Based Simulation (O(n^2) time, O(n) space)

Instead of rebuilding the array each time, compute prefix sums and simulate the effect of multiplying a candidate subarray. Fix the start index l, extend the end index r, and dynamically track how the multiplied segment affects the total. For each pair (l, r), combine the multiplied segment contribution with the best prefix and suffix subarray sums. This reduces redundant recomputation but still requires checking O(n^2) candidate segments. Useful for reasoning about the structure of the optimal solution before implementing a linear-time method.

Approach 3: Dynamic Programming with Kadane States (O(n) time, O(1) space)

The optimal solution tracks three running states while iterating through the array. State 1: the maximum subarray sum ending at index i without using the multiplier. State 2: the maximum subarray sum where the multiplier is currently being applied. State 3: the maximum subarray sum where the multiplier has already been used and the subarray continues normally. Each step updates these states using transitions similar to Kadane's algorithm. For example, when entering the multiplied segment, multiply the current element before adding it to the running sum. This state-machine view ensures the multiplier is applied to exactly one contiguous segment while maintaining linear time.

The key insight: the optimal solution can be expressed as transitions between three phases—before multiplication, during multiplication, and after multiplication. Maintaining these states while scanning once avoids explicitly enumerating subarrays. This pattern is common in dynamic programming problems involving a single modification to a subarray and builds directly on techniques used for array optimization problems.

Recommended for interviews: The linear dynamic programming approach with Kadane-style state transitions is the expected solution. Interviewers like it because it demonstrates that you can convert a brute-force subarray modification problem into a constant-state DP scan. Mentioning the brute force approach first shows understanding of the search space, but implementing the O(n) DP proves algorithmic maturity.