Q2. Write a Python function that takes a list of integers and returns the second largest number in the list. If there are no second largest numbers, the function should return None.

For example, if the input list is [1, 2, 3, 4, 5], the function should return 4 (which is the second largest number in the list).

Note: The list can have both negative and positive integers.

Answer: -

We need to find the second largest number in the given list.

We can do this by iterating through the list and keeping track of the largest and second largest numbers seen so far.

Algorithm:

1. Initialise the largest and second largest variables to None.

2. Iterate through the list and compare each number with the largest and second largest variables.

3. If a number is greater than the largest variable, update the second largest variable to the value of the largest variable and update the largest variable to the current number.

4. If a number is less than or equal to the largest variable but greater than the second largest variable, update the second largest variable to the current number.

5. Return the value of the second largest variable.

Sample Python Code -

def second_largest(nums):
    largest = None
    second_largest = None
    for num in nums:
        if largest is None or num > largest:
            second_largest = largest
            largest = num
        elif second_largest is None or num > second_largest:
            second_largest = num
    return second_largest

Let's break down the code and explain how it works:

• largest and second_largest are initialised to None.
• The for loop iterates through each number in the given list.
• The first if statement checks if the current number is greater than the current largest number. If it is, the second largest number is updated to the value of the current largest number and the largest number is updated to the current number.
• The second elif statement checks if the current number is less than or equal to the current largest number but greater than the current second largest number. If it is, the second largest number is updated to the current number.
• The return statement returns the value of the second largest variable.

Sample inputs and outputs -

print(second_largest([1, 2, 3, 4, 5]))    # Output: 4
print(second_largest([5, 4, 3, 2, 1]))    # Output: 4
print(second_largest([1, 1, 2, 2, 3, 3]))  # Output: 2
print(second_largest([1]))                # Output: None

I hope you find this useful.

Q3. Given a list of integers, write a Python function find_largest_subarray_sum(arr) that finds the largest sum of a continuous subarray using the Divide and Conquer approach. The function should return the largest sum found.

I've added comments to the code. Let me know if you do not understand any of it. The code is straightforward. Note - this is a difficult question. It's likely that you won't find questions of this difficulty in TCS XPlore.

Pay attention to the logic.

def find_largest_subarray_sum(arr):
    def cross_sum(arr, low, mid, high):
        # Initialize the sum of the left and right subarrays
        left_sum = float('-inf')
        right_sum = float('-inf')

        # Calculate the sum of the left subarray
        curr_sum = 0
        for i in range(mid, low - 1, -1):
            curr_sum += arr[i]
            if curr_sum > left_sum:
                left_sum = curr_sum

        # Calculate the sum of the right subarray
        curr_sum = 0
        for i in range(mid + 1, high + 1):
            curr_sum += arr[i]
            if curr_sum > right_sum:
                right_sum = curr_sum

        # Return the sum of the left and right subarrays
        return left_sum + right_sum

    def max_subarray_sum(arr, low, high):
        # Base case: if there's only one element, return the element
        if low == high:
            return arr[low]

        # Calculate the middle index
        mid = (low + high) // 2

        # Recursively find the largest sum in the left, right, and cross subarrays
        left_sum = max_subarray_sum(arr, low, mid)
        right_sum = max_subarray_sum(arr, mid + 1, high)
        cross_sum_ = cross_sum(arr, low, mid, high)

        # Return the largest sum among the three subarrays
        return max(left_sum, right_sum, cross_sum_)

    # Call the helper function with initial low and high indices
    return max_subarray_sum(arr, 0, len(arr) - 1)


# Example usage
arr = [2, -4, 5, -8, 7, -1, 3, -2]
result = find_largest_subarray_sum(arr)
print(f"The largest sum of a continuous subarray is: {result}")