Maximum Subarray - Leetcode Solution

The Maximum Subarray problem is a classic problem in computer science that is often asked in programming interviews. In this problem, we are given an array of integers, and we have to find the contiguous subarray that has the largest sum.

For example, if we are given the array [−2,1,−3,4,−1,2,1,−5,4], then the contiguous subarray with the largest sum is [4,−1,2,1], and its sum is 6.

To solve this problem, we can use the Kadane's algorithm. The algorithm is based on the observation that a subarray with the largest sum must end at one of the array elements. Therefore, we can iteratively calculate the maximum sum of all subarrays ending at each element of the array, and return the maximum of these sums.

Here is the step-by-step algorithm to solve the Maximum Subarray problem for the given array:

1. Initialize two variables max_so_far and max_ending_here to 0.
2. Iterate through the array from start to end.
3. For each element in the array, add it to max_ending_here.
4. If max_ending_here becomes negative, set it to 0.
5. If max_ending_here is greater than max_so_far, set max_so_far to max_ending_here.
6. Return max_so_far as the result.

Let's implement this algorithm in Python:

def maxSubArray(nums):
    max_so_far = 0
    max_ending_here = 0
    for num in nums:
        max_ending_here += num
        if max_ending_here < 0:
            max_ending_here = 0
        elif max_ending_here > max_so_far:
            max_so_far = max_ending_here
    return max_so_far

We can test this function with the example array:

>>> maxSubArray([-2,1,-3,4,-1,2,1,-5,4])
6

The function correctly returns the maximum sum of the contiguous subarray.

This algorithm has a time complexity of O(n), where n is the length of the array. This is because we iterate through the array only once. Therefore, this algorithm is very efficient and can be used to solve the Maximum Subarray problem for very large arrays.

1