Dare2Solve
To solve the problem of maximizing the total cost of subarrays, we need to understand the behavior of the cost function:
cost(l, r)
alternates signs based on the indices l
and r
.Dynamic Programming Approach:
dp
where dp[i]
represents the maximum total cost that can be achieved up to index i
in the array nums
.Initialization:
dp[0] = 0
because if no split is made, the entire array contributes zero cost.Iterative Calculation:
i
from 1
to n-1
.i
, compute the potential maximum cost by considering splitting at every previous index j
(0 <= j < i
) and update dp[i]
accordingly.Cost Function:
j
using the formula provided (cost(j, i-1)
where j < i
).Result:
dp[n-1]
.Time Complexity: O(n)
n
iterations) to compute the dp
array.Space Complexity: O(n)
dp
array of size n
.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.
class Solution {
public:
long long maximumTotalCost(vector<int>& nums) {
int n = nums.size();
vector<long long> 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];
}
};
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]
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];
}
}
/**
* @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];
};
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
}
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];
}
}