Alternating Sum Subarray Maximum — Problem Statement & Solution Guide
ArraysMediumAlternating sum subarray
TimeO(n)
|SpaceO(1)
Problem Description
Given an array of integers, find the maximum sum of a subarray where the signs of the elements alternate, ending with either a positive or negative value.
Examples
Example 1
Input
[1, -2, 3, -4, 5]
Output
2
Explanation: Step-by-step: with input [1, -2, 3, -4, 5], we first find all possible subarrays with alternating signs. Then, we calculate the sum of each subarray. Finally, we return the maximum sum, which is 2.
Example 2
Input
[2, 4, -3, -1, 5]
Output
7
Explanation: Step-by-step: with input [2, 4, -3, -1, 5], we first find all possible subarrays with alternating signs. Then, we calculate the sum of each subarray. Finally, we return the maximum sum, which is 7.
Constraints
- Input array will have at least one element and at most 100 elements.
- Each element in the array will be an integer between -1000 and 1000.
Verified Code Solutions
JavaScript Solution
Time: O(n)
function maxAlternatingSum(arr) { if (arr.length === 0) return 0; let maxSum = -Infinity; for (let i = 0; i < arr.length; i++) { let sum = 0; let sign = 1; for (let j = i; j < arr.length; j++) { sum += sign * arr[j]; sign *= -1; if (sign === 1) { maxSum = Math.max(maxSum, sum); } else { maxSum = Math.max(maxSum, -sum); } } } return maxSum; }class Solution {
public int solution(int[] nums) {
int max_sum = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int current_sum = 0;
for (int j = i; j < nums.length; j++) {
if ((j - i) % 2 == 0) {
current_sum += nums[j];
} else {
current_sum -= nums[j];
}
max_sum = Math.max(max_sum, current_sum);
}
}
return max_sum;
}
}def solution(nums):
max_sum = float('-inf')
for i in range(len(nums)):
current_sum = 0
for j in range(i, len(nums)):
if (j - i) % 2 == 0:
current_sum += nums[j]
else:
current_sum -= nums[j]
max_sum = max(max_sum, current_sum)
return max_sumfunction maxAlternatingSum(arr) { if (arr.length === 0) return 0; let maxSum = -Infinity; for (let i = 0; i < arr.length; i++) { let sum = 0; let sign = 1; for (let j = i; j < arr.length; j++) { sum += sign * arr[j]; sign *= -1; if (sign === 1) { maxSum = Math.max(maxSum, sum); } else { maxSum = Math.max(maxSum, -sum); } } } return maxSum; }Asked in Top Tech Interviews
SalesforceMicrosoft
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.