Maximum Subarray medium

Problem Statement

Find the contiguous subarray within an array (containing at least one number) which has the largest sum and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1] Output: 1

Example 3:

Input: nums = [5,4,-1,7,8] Output: 23

Steps

The most efficient approach to solve this problem is Kadane's Algorithm. The algorithm iterates through the array, keeping track of the current maximum sum and the overall maximum sum.

1. Initialization: Initialize two variables: maxSoFar (to store the overall maximum sum) and maxEndingHere (to store the maximum sum ending at the current position). Both are initialized to the first element of the array.

2. Iteration: Iterate through the array from the second element.

3. Update maxEndingHere: For each element, update maxEndingHere as follows:

   • If maxEndingHere is positive, add the current element to it.
   • If maxEndingHere is negative or zero, it means the current element starts a new potentially larger sum, so set maxEndingHere to the current element.

4. Update maxSoFar: After updating maxEndingHere, compare it with maxSoFar. If maxEndingHere is greater than maxSoFar, update maxSoFar to maxEndingHere.

5. Return maxSoFar: After iterating through the entire array, maxSoFar will contain the maximum subarray sum.

Explanation

Kadane's algorithm cleverly avoids the need to check all possible subarrays. By only keeping track of the maximum sum ending at the current position, it efficiently identifies the overall maximum sum. If the current maximum sum (maxEndingHere) becomes negative, it means that including the previous elements is detrimental to the overall sum; therefore, a new subarray starting from the current element is considered.

Code

function maxSubArray(nums: number[]): number {
    let maxSoFar = nums[0];
    let maxEndingHere = nums[0];

    for (let i = 1; i < nums.length; i++) {
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
};

Complexity

• Time Complexity: O(n), where n is the length of the input array. The algorithm iterates through the array once.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space to store the variables maxSoFar and maxEndingHere.