Coding Interview Questions | Maximum Subarray

January 5th, 2024

Contains Duplicate Problem Introduction:

This summary will talk about my solution to the maximum subarray problem as seen on leetcode here.

How do you solve the Maximum Subarrary Problem in O(n) time?:

Solution:

function maxSubArray(nums: number[]): number {
  if (nums.length === 1) {
    return nums[0];
  }

  const maxSums = Array.from(nums, () => 0);
  maxSums[0] = nums[0];

  // Create array of maximum sums
  for (let numIdx = 1; numIdx < maxSums.length; numIdx++) {
    const currentNum = nums[numIdx];

    maxSums[numIdx] = Math.max(currentNum, currentNum + maxSums[numIdx - 1]);
  }

  return Math.max(...maxSums);
}

Maximum Subarray Solution Summary:

Below is a breakdown of the key aspects of the solution above:

1. Base Case Handling: The algorithm checks if the length of the input array (nums) is 1. If true, it directly returns the only element in the array as the maximum subarray sum.
2. Dynamic Programming Approach: The solution utilizes a dynamic programming approach, creating an array (maxSums) to store the maximum sum at each index.
3. Maximum Sum Calculation: The algorithm iterates through the array, updating maxSums at each index with the maximum sum considering the current element and the maximum sum from the previous index.
4. Final Maximum Subarray Sum Determination: The final result is determined by finding the maximum value in the maxSums array.

Complexities

1. Time Complexity: The time complexity of the solution is O(n), where n is the length of the input array.
2. Space Complexity: The space complexity of the solution is O(n) as it uses an additional array (maxSums) of the same length as the input array.