Alternating Sum Maximization 2 — Problem Statement & Solution Guide
ArraysMediumMixed
TimeO(n)
|SpaceO(1)
Problem Description
Given an array of integers values, find the maximum total value that can be obtained by alternating between adding and subtracting consecutive elements. The sequence of additions and subtractions must start with an addition.
Examples
Example 1
Input
[12, -34, 5]
Output
-27
Explanation: Step-by-step: Given array [12, -34, 5], we start with addition: 12 + (-34) = -22. Then, we subtract: -22 - 5 = -27.
Example 2
Input
[-12, -34, 5]
Output
-51
Explanation: Step-by-step: Given array [-12, -34, 5], we start with addition: -12 + (-34) = -46. Then, we subtract: -46 - 5 = -51.
Constraints
- 1 <= array length <= 1000
- -1000 <= array element <= 1000
Verified Code Solutions
JavaScript Solution
Time: O(n)
function alternatingSumMaximization2(values) {
if (values.length === 0) return 0;
let sum = values[0];
let min = Infinity;
let add = true;
for (let i = 1; i < values.length; i++) {
if (add) {
sum += values[i];
} else {
sum = Math.max(sum - values[i], min + values[i]);
min = Math.min(min, sum - values[i]);
}
add = !add;
}
return sum;
}class Solution {
public int alternatingSumMaximization(int[] nums) {
if (nums.length == 0) {
return 0;
}
int result = nums[0];
for (int i = 1; i < nums.length; i++) {
if (i % 2 == 1) {
result += nums[i];
} else {
result -= nums[i];
}
}
return result;
}
}def alternating_sum_maximization(nums):
if not nums:
return 0
result = nums[0]
for i in range(1, len(nums)):
if i % 2 == 1:
result += nums[i]
else:
result -= nums[i]
return resultfunction alternatingSumMaximization2(values) {
if (values.length === 0) return 0;
let sum = values[0];
let min = Infinity;
let add = true;
for (let i = 1; i < values.length; i++) {
if (add) {
sum += values[i];
} else {
sum = Math.max(sum - values[i], min + values[i]);
min = Math.min(min, sum - values[i]);
}
add = !add;
}
return sum;
}Asked in Top Tech Interviews
PhonePePayPal
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.