1. Problem Description
You wake up to find your future self standing in front of you, having traveled back in time with a list of the daily stock market movement information of a particular stock/ETF. He provides you with this list and instructs you to use it to get rich. However, to avoid suspicion of insider trading, you can only place two orders: a buy order at 9:00 am and a sell order on or after the buying day at 3:30 pm. Your transactions must blend in with the crowd, ensuring minimal attention. This constraint means your net profit will also include any loss on intermediate days if the stock's performance fluctuates.
Your objective is to find the best day to buy and the best day to sell, given the information provided.
The task is to calculate the total profit (or loss, if negative) you would make if you buy x shares of the stock.
1.1 Input Format
The first line of input is t, the number of test cases. Each test case consists of two lines of input:
- First line: Two space-separated integers n and x
- Second line: n space-separated integers, represented as Vi, which is the price increase (or decrease if negative) per share of that stock on the ith day.
Put simply, Vi is the value calculated as \( C_i - O_i \) where Ci is the closing price of the stock on the ith day, and Oi is the opening price of the stock on the same day.
1.2 Constraints
- 1 ≤ t ≤ 104
- 1 ≤ n ≤ 103
- 1 ≤ x ≤ 108
- -103 ≤ Vi ≤ 103 for all i ∈ [1, n]
1.3 Output Format
For each test case, output a single integer representing the total profit or loss you will make if you buy and sell on the optimal days.
1.4 Sample Input
2
9 10
-2 1 -3 4 -1 2 1 -5 4
5 5
5 4 -1 7 8
1.5 Sample Output
60
115
1.6 Explanation
- For the first test case, the best time to buy and sell is when the price changes are 4, -1, 2, and 1, giving a total profit of 4 - 1 + 2 + 1 = 6. Since you buy 10 shares, the total profit is 60.
- For the second test case, the best strategy is to buy and sell from the start till the end, yielding a total profit of 23. With 5 shares, the total profit is 115.
Solution
# Read the number of test cases (t) from user input
t = int(input())
# Loop through each test case
for _ in range(t):
# Read two integers n and x from user input. n is the size of the array, x is a multiplier.
n, x = map(int, input().split())
# Read the array of integers from user input
arr = list(map(int, input().split()))
# Initialize variables for Kadane's algorithm to find the maximum subarray sum
max_so_far = arr[0] # Stores the maximum sum found so far
max_ending_here = arr[0] # Stores the maximum sum of the subarray ending at the current position
start = 0 # Start index of the maximum subarray
end = 0 # End index of the maximum subarray
temp_start = 0 # Temporary start index for the current subarray
# Iterate through the array starting from the second element
for i in range(1, n):
# Update the maximum sum of the subarray ending here. It can either include the current element in the previous subarray
# or start a new subarray from the current element.
max_ending_here = max(max_ending_here + arr[i], arr[i])
# If the new subarray sum is greater than the maximum found so far, update max_so_far
if max_ending_here > max_so_far:
max_so_far = max_ending_here
start = temp_start # Update the start index of the maximum subarray
end = i # Update the end index of the maximum subarray
# If the current subarray sum becomes negative, reset it and update the temporary start index
if max_ending_here < 0:
max_ending_here = 0
temp_start = i + 1 # Update temp_start to the next index
# Calculate the total sum of the array
total_sum = sum(arr)
# Calculate the maximum profit by taking the maximum of max_so_far (best subarray) and total_sum (entire array)
max_profit = max(max_so_far, total_sum)
# Print the maximum profit multiplied by x
print(max_profit * x)
Sample Solution Provided by Instructor
def maxSubArray(nums):
# Initialize 'maxSum' to the first element of the array 'nums'.
# This will keep track of the maximum sum of any subarray found so far.
maxSum = nums[0]
# Initialize 'currentSum' to the first element of the array 'nums'.
# This will track the current subarray sum as we iterate through 'nums'.
currentSum = nums[0]
# Iterate through the elements of 'nums', starting from the second element.
for num in nums[1:]:
# Update 'currentSum' to be either the current element 'num' (starting a new subarray)
# or 'currentSum + num' (continuing the current subarray), whichever is larger.
currentSum = max(num, currentSum + num)
# Update 'maxSum' to be the maximum of itself or 'currentSum'.
# This ensures that 'maxSum' always holds the highest sum found so far.
maxSum = max(maxSum, currentSum)
# Return the maximum subarray sum found.
return maxSum
# Read the number of test cases.
t = int(input())
# Loop through each test case.
for _ in range(t):
# Read two integers 'n' and 'x' from the input.
# 'n' is the size of the array, and 'x' is a multiplier.
n, x = map(int, input().split())
# Read the list of integers 'nums', which represents the array of numbers.
nums = list(map(int, input().split()))
# Call 'maxSubArray' to find the maximum subarray sum and multiply it by 'x'.
print(maxSubArray(nums) * x)