Technical Interview Question:

Consider an array of integers, nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the largest sum of a contiguous subarray is 6, which corresponds to the subarray [4, -1, 2, 1]. Therefore, the expected output is 6.

Write a function maxSubarray to find the maximum sum of a contiguous subarray.

Function Signature:

def maxSubarray(nums: List[int]) -> int:

Answer:

In this problem, we will use the Kadane's algorithm, which is an efficient algorithm to solve the maximum subarray problem. Kadane's algorithm follows a dynamic programming approach and has a time complexity of O(n), where n is the length of the input array.

We'll initialize two variables, max_so_far and max_ending_here, both initially set to the first element of the array. We iterate over the array starting from the second element. At each iteration, we update max_ending_here by taking the maximum between the current element and the sum of the current element and max_ending_here. If max_ending_here becomes negative, we reset it to 0. Then, we update max_so_far by taking the maximum between max_so_far and max_ending_here.

Let's implement the solution:

from typing import List

def maxSubarray(nums: List[int]) -> int:
    n = len(nums)
    if n == 0:
        return 0
    
    max_so_far = nums[0]      # Initialize the maximum sum
    max_ending_here = nums[0] # Initialize the sum of current subarray
    
    for i in range(1, n):
        max_ending_here = max(nums[i], max_ending_here + nums[i])
        max_so_far = max(max_so_far, max_ending_here)
    
    return max_so_far

Now, let's test the function with the given example:

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = maxSubarray(nums)
print(max_sum)

Output:

6

The function returns the correct output for the given example. It finds the maximum sum of a contiguous subarray, which is 6.

The time complexity of this solution is O(n), where n is the length of the input array nums. This is because we perform a single pass over the array, comparing and updating the maximum sums. The space complexity is O(1), as we only use a constant amount of additional space for the variables max_so_far and max_ending_here.