Maximum Subarray medium

Problem Statement

Find the contiguous subarray within a one-dimensional 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: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Steps

The problem can be solved efficiently using Kadane's Algorithm. The core idea is to maintain a current_max variable that tracks the maximum sum ending at the current position. We also maintain a global_max variable to store the overall maximum sum encountered so far.

1. Initialization: Set current_max and global_max to the first element of the array.
2. Iteration: Iterate through the array starting from the second element.
3. Update current_max: For each element, decide whether to extend the current subarray (by adding the current element to current_max) or start a new subarray (by setting current_max to the current element). We choose the option that yields a larger sum.
4. Update global_max: Compare current_max with global_max and update global_max if current_max is larger.
5. Return: After iterating through the entire array, return global_max.

Explanation

Kadane's Algorithm cleverly avoids the need to explore all possible subarrays, which would lead to an O(n^2) time complexity. By iteratively building the current_max, we efficiently find the optimal subarray. If current_max becomes negative, it means that extending the current subarray would only decrease the sum, so it's better to start a new subarray from the next element.

Code

def max_sub_array(nums):
    """
    Finds the maximum sum of a contiguous subarray.

    Args:
        nums: A list of integers.

    Returns:
        The maximum sum of a contiguous subarray.
    """
    current_max = nums[0]
    global_max = nums[0]

    for i in range(1, len(nums)):
        current_max = max(nums[i], current_max + nums[i])
        global_max = max(global_max, current_max)

    return global_max

Complexity

• Time Complexity: O(n), as we iterate through the array once.
• Space Complexity: O(1), as we use only a constant amount of extra space to store current_max and global_max.