Maximum Alternating Profit ā Problem Statement & Solution Guide
Problem Description
In a galaxy with fluctuating resource prices, find the maximum profit that can be achieved by trading resources along a route where the price difference between each pair of consecutive resources alternates between positive and negative. If no such route exists, return 0.
Examples
Input
[6, 4, 2, 3, 2]
Output
4
Explanation: Step-by-step: with input [6, 4, 2, 3, 2], we first calculate the differences between consecutive numbers: [6-4=2, 4-2=2, 2-3=-1, 3-2=1]. Since the differences alternate between positive and negative, we can achieve a profit of 2 by choosing the first 2 numbers and then the last 2 numbers.
Input
[-1, -1, 0, -1]
Output
0
Explanation: Step-by-step: with input [-1, -1, 0, -1], we first calculate the differences between consecutive numbers: [-1-(-1)=0, -1-0=-1, 0-(-1)=1]. Since the differences do not alternate between positive and negative, the maximum profit is indeed 0.
Constraints
- The input array contains at least 2 and no more than 1000 elements.
- Each element in the array is between -1000 and 1000.
Optimal Approach & Strategy
The optimized approach uses prefix sums and sign tracking to find the maximum subarray sum with alternating signs in linear time, O(n), by iterating through the array and maintaining variables to track the maximum sum and the sign of the previous difference.
Brute Force Approach
The brute-force approach involves checking every possible subarray and calculating the sum of its elements, resulting in a time complexity of O(nĀ²). This approach is inefficient for large inputs and can be improved using prefix sums and sign tracking.
Verified Code Solutions
function maxAlternatingProfit(prices) { if (prices.length < 3) return 0; let maxProfit = 0; let buy = prices[0]; let isPositive = true; for (let i = 1; i < prices.length; i++) { if (isPositive && prices[i] > prices[i-1]) { maxProfit += prices[i] - buy; buy = prices[i]; isPositive = false; } else if (!isPositive && prices[i] < prices[i-1]) { maxProfit += prices[i] - buy; buy = prices[i]; isPositive = true; } else if (prices[i] === prices[i-1]) { return 0; } } return maxProfit; }class Solution {
public int maxAlternatingProfit(int[] nums) {
if (nums.length < 2) {
return 0;
}
int max_profit = 0;
for (int i = 1; i < nums.length; i++) {
if ((nums[i] - nums[i - 1]) * ((i % 2) * 2 - 1) > 0) {
max_profit += nums[i] - nums[i - 1];
}
}
return max_profit;
}
}def maxAlternatingProfit(nums):
if len(nums) < 2:
return 0
max_profit = 0
for i in range(1, len(nums)):
if (nums[i] - nums[i - 1]) * ((i % 2) * 2 - 1) > 0:
max_profit += nums[i] - nums[i - 1]
return max_profitfunction maxAlternatingProfit(prices) { if (prices.length < 3) return 0; let maxProfit = 0; let buy = prices[0]; let isPositive = true; for (let i = 1; i < prices.length; i++) { if (isPositive && prices[i] > prices[i-1]) { maxProfit += prices[i] - buy; buy = prices[i]; isPositive = false; } else if (!isPositive && prices[i] < prices[i-1]) { maxProfit += prices[i] - buy; buy = prices[i]; isPositive = true; } else if (prices[i] === prices[i-1]) { return 0; } } return maxProfit; }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.