🎨Now live: Try our Free AI Image Generation Feature

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 indicesl
andr
. - 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
- Dynamic Programming Approach:
- Use a dynamic programming array
dp
wheredp[i]
represents the maximum total cost that can be achieved up to indexi
in the arraynums
. - Initialization:
- Start by initializing
dp[0] = 0
because if no split is made, the entire array contributes zero cost. - Iterative Calculation:
- Iterate through each index
i
from1
ton-1
. - For each indexi
, compute the potential maximum cost by considering splitting at every previous indexj
(0 <= j < i
) and updatedp[i]
accordingly. - Cost Function:
- Compute the contribution of splitting at each point
j
using the formula provided (cost(j, i-1)
wherej < i
). - 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 thedp
array. - Each computation for a given index involves a constant amount of work. - Space Complexity:
O(n)
- Additional space is used for thedp
array of sizen
.
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];
}
}