3196. Maximize Total Cost of Alternating Subarrays LeetCode Solution
In this guide, you will get 3196. Maximize Total Cost of Alternating Subarrays LeetCode Solution with the best time and space complexity. The solution to Maximize Total Cost of Alternating Subarrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximize Total Cost of Alternating Subarrays
You are given an integer array nums with length n.
The cost of a subarray nums[l..r], where 0 <= l <= r 1, at indices i1, i2, …, ik − 1, where 0 <= i1 < i2 < … < ik – 1 < n – 1, then the total cost will be:
cost(0, i1) + cost(i1 + 1, i2) + … + cost(ik − 1 + 1, n − 1)
Return an integer denoting the maximum total cost of the subarrays after splitting the array optimally.
Note: If nums is not split into subarrays, i.e. k = 1, the total cost is simply cost(0, n – 1).
Example 1:
Input: nums = [1,-2,3,4]
Output: 10
Explanation:
One way to maximize the total cost is by splitting [1, -2, 3, 4] into subarrays [1, -2, 3] and [4]. The total cost will be (1 + 2 + 3) + 4 = 10.
Example 2:
Input: nums = [1,-1,1,-1]
Output: 4
Explanation:
One way to maximize the total cost is by splitting [1, -1, 1, -1] into subarrays [1, -1] and [1, -1]. The total cost will be (1 + 1) + (1 + 1) = 4.
Input: nums = [0]
Output: 0
Explanation:
We cannot split the array further, so the answer is 0.
Example 4:
Input: nums = [1,-1]
Output: 2
Explanation:
Selecting the whole array gives a total cost of 1 + 1 = 2, which is the maximum.
Constraints:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
3196. Maximize Total Cost of Alternating Subarrays LeetCode Solution in C++
class Solution {
public:
long long maximumTotalCost(vector<int>& nums) {
long keep = nums[0]; // the maximum cost if the last number is kept
long flip = nums[0]; // the maximum cost if the last number is flipped
for (int i = 1; i < nums.size(); ++i) {
const long keepCurr = max(keep, flip) + nums[i];
const long flipCurr = keep - nums[i];
keep = keepCurr;
flip = flipCurr;
}
return max(keep, flip);
}
}; /* code provided by PROGIEZ */
3196. Maximize Total Cost of Alternating Subarrays LeetCode Solution in Java
class Solution {
public long maximumTotalCost(int[] nums) {
long keep = nums[0]; // the maximum cost if the last number is kept
long flip = nums[0]; // the maximum cost if the last number is flipped
for (int i = 1; i < nums.length; ++i) {
final long keepCurr = Math.max(keep, flip) + nums[i];
final long flipCurr = keep - nums[i];
keep = keepCurr;
flip = flipCurr;
}
return Math.max(keep, flip);
}
} // code provided by PROGIEZ
3196. Maximize Total Cost of Alternating Subarrays LeetCode Solution in Python
class Solution:
def maximumTotalCost(self, nums: list[int]) -> int:
keep = nums[0] # the maximum cost if the last number is kept
flip = nums[0] # the maximum cost if the last number is flipped
for i in range(1, len(nums)):
keepCurr = max(keep, flip) + nums[i]
flipCurr = keep - nums[i]
keep = keepCurr
flip = flipCurr
return max(keep, flip) # code by PROGIEZ
