Alternating Budget Accumulation — Problem Statement & Solution Guide
Problem Description
Given an array of integers budget where positive values represent excess funds and negative values represent shortfalls, determine the maximum possible sum of alternating budget intervals where the first interval has excess funds, the second has a shortfall, and this pattern continues.
Examples
Input
[1, -2, 3, -4, 5]
Output
5
Explanation: Step-by-step: with input [1, -2, 3, -4, 5], we first initialize max_sum as -inf. Then we iterate through the array, and for each element, we check if it's positive (excess funds). If it is, we update max_sum as max(max_sum, current_sum). If it's negative (shortfall), we update max_sum as max(max_sum, current_sum - current_element). Finally, we return max_sum, which is 5.
Input
[-1, 2, -3, 4, -5]
Output
4
Explanation: Step-by-step: with input [-1, 2, -3, 4, -5], we first initialize max_sum as -inf. Then we iterate through the array, and for each element, we check if it's positive (excess funds). If it is, we update max_sum as max(max_sum, current_sum). If it's negative (shortfall), we update max_sum as max(max_sum, current_sum - current_element). Finally, we return max_sum, which is 4.
Constraints
- 1 <= array length <= 1000
- -1000 <= array element <= 1000
Verified Code Solutions
class Solution {
public int solution(int[] budget) {
int maxSum = Integer.MIN_VALUE;
int currentSum = 0;
for (int num : budget) {
if (num > 0) {
currentSum = Math.max(currentSum, num);
} else {
currentSum -= num;
maxSum = Math.max(maxSum, currentSum);
}
}
return Math.max(maxSum, currentSum);
}
}def solution(budget):
max_sum = float('-inf')
current_sum = 0
for num in budget:
if num > 0:
current_sum = max(current_sum, num)
else:
current_sum -= num
max_sum = max(max_sum, current_sum)
return max(max_sum, current_sum)Asked in Top Tech Interviews
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.