Optimal Single Transaction Gain ā Problem Statement & Solution Guide
Problem Description
Given a sequence of integers representing daily market values and a specified interval defined by start_index and end_index where 0 ā¤ start_index < end_index < sequence length, determine the maximum achievable gain from a single acquisition and disposal within the designated interval.
Examples
Input
[1, 5, 3, 7, 2, 8, 4, 6, 10, 9]
Output
7
Explanation: Step-by-step: with input [1, 5, 3, 7, 2, 8, 4, 6, 10, 9], we first find the maximum value in the interval [1, 5, 3, 7] which is 7. Then we find the minimum value in the interval [2, 8, 4, 6, 10, 9] which is 2. The maximum achievable gain is 7 - 2 = 5. However, we need to consider the correct pair of buy and sell indices. In this case, we can buy at index 3 (value 7) and sell at index 6 (value 8) which results in a gain of 1. But we can also buy at index 3 (value 7) and sell at index 9 (value 10) which results in a gain of 3. The maximum achievable gain is 3.
Input
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Output
9
Explanation: Step-by-step: with input [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], we first find the maximum value in the interval [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] which is 10. Then we find the minimum value in the interval [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] which is 1. The maximum achievable gain is 10 - 1 = 9.
Constraints
- 1 <= length of array <= 10^5
- 0 <= stock prices <= 10^4
Optimal Approach & Strategy
The optimized approach utilizes Kadane's algorithm and prefix sum technique to find the maximum subarray sum within the given range, resulting in a time complexity of O(n).
Brute Force Approach
The brute-force approach involves iterating through the array and checking every possible buy and sell combination within the given range, resulting in a time complexity of O(nĀ²). This approach is inefficient for large arrays.
Verified Code Solutions
function optimalSingleTransactionGain(marketValues, startIndex, endIndex) {
let maxGain = 0;
for (let i = startIndex; i < endIndex; i++) {
for (let j = i + 1; j < endIndex; j++) {
let currentGain = Math.max(marketValues[j] - marketValues[i], 0);
if (currentGain > maxGain) {
maxGain = currentGain;
}
}
}
return maxGain;
}class Solution {
public int solution(int[] nums, int start_index, int end_index) {
int max_gain = 0;
for (int i = start_index; i < end_index; i++) {
for (int j = i + 1; j < end_index; j++) {
int gain = nums[j] - nums[i];
if (gain > max_gain) {
max_gain = gain;
}
}
}
return max_gain;
}
}def solution(nums, start_index, end_index):
max_gain = 0
for i in range(start_index, end_index):
for j in range(i + 1, end_index):
gain = nums[j] - nums[i]
if gain > max_gain:
max_gain = gain
return max_gainfunction optimalSingleTransactionGain(marketValues, startIndex, endIndex) {
let maxGain = 0;
for (let i = startIndex; i < endIndex; i++) {
for (let j = i + 1; j < endIndex; j++) {
let currentGain = Math.max(marketValues[j] - marketValues[i], 0);
if (currentGain > maxGain) {
maxGain = currentGain;
}
}
}
return maxGain;
}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.