3196. Maximize Total Cost of Alternating Subarrays

Intuition and Approach

Problem Understanding

To solve the problem of maximizing the total cost of subarrays, we need to understand the behavior of the cost function:

• The cost function cost(l, r) alternates signs based on the indices l and r.
• To maximize the total cost, we need to strategically split the array into subarrays such that the positive contributions from the cost function are maximized.

Strategy

1. Dynamic Programming Approach: - Use a dynamic programming array dp where dp[i] represents the maximum total cost that can be achieved up to index i in the array nums.
2. Initialization: - Start by initializing dp[0] = 0 because if no split is made, the entire array contributes zero cost.
3. Iterative Calculation: - Iterate through each index i from 1 to n-1. - For each index i, compute the potential maximum cost by considering splitting at every previous index j (0 <= j < i) and update dp[i] accordingly.
4. Cost Function: - Compute the contribution of splitting at each point j using the formula provided (cost(j, i-1) where j < i).
5. Result: - The maximum total cost after optimal splitting will be stored in dp[n-1].

Time Complexity

• Time Complexity: O(n) - This is because we iterate through the array once (n iterations) to compute the dp array. - Each computation for a given index involves a constant amount of work.
• Space Complexity: O(n) - Additional space is used for the dp array of size n.

Conclusion

This approach efficiently computes the maximum total cost of subarrays by leveraging dynamic programming to handle the complexities of the cost function. By iterating through the array and updating the dp array, we ensure that each element is assigned to exactly one subarray while maximizing the overall cost.

Code

C++

class Solution {
public:
    long long maximumTotalCost(vector& nums) {
        int n = nums.size();
        vector dp(n + 1, -LLONG_MAX);
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 1; i < n; ++i) {
            dp[i + 1] = max(dp[i] + nums[i], dp[i - 1] + nums[i - 1] - nums[i]);
        }
        return dp[n];
    }
};

Python

class Solution:
    def maximumTotalCost(self, nums):
        n = len(nums)
        dp = [0] * (n + 1)
        dp[1] = nums[0]
        for i in range(1, n):
            dp[i + 1] = max(dp[i] + nums[i], dp[i - 1] + nums[i - 1] - nums[i])
        return dp[n]

Java

class Solution {
    public long maximumTotalCost(int[] nums) {
        int n = nums.length;
        long[] dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 1; i < n; ++i) {
            dp[i + 1] = Math.max(dp[i] + nums[i], dp[i - 1] + nums[i - 1] - nums[i]);
        }
        return dp[n];
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumTotalCost = function (nums) {
  var dp = new Array(nums.length + 1);
  dp[0] = 0;
  dp[1] = nums[0];
  for (var i = 1; i < nums.length; ++i) {
    dp[i + 1] = Math.max(dp[i] + nums[i], dp[i - 1] + nums[i - 1] - nums[i]);
  }
  return dp[nums.length];
};

Go

func maximumTotalCost(nums []int) int64 {
	n := len(nums)
	dp := make([]int64, n+1)
	dp[1] = int64(nums[0])
	for i := 1; i < n; i++ {
		dp[i+1] = max(dp[i]+int64(nums[i]), dp[i-1]+int64(nums[i-1])-int64(nums[i]))
	}
	return dp[n]
}

func max(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

C#

public class Solution {
    public long MaximumTotalCost(int[] nums) {
        int n = nums.Length;
        long[] dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 1; i < n; ++i) {
            dp[i + 1] = Math.Max(dp[i] + nums[i], dp[i - 1] + nums[i - 1] - nums[i]);
        }
        return dp[n];
    }
}