Week 3 - Assignment 2 - CS103 - Swayam

Week 3 - Assignment 2

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:

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.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

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)