Problem Statement

Given an integer array nums, find the subarray with the largest sum, and return its sum.

A subarray is a contiguous non-empty sequence of elements within an array.

Additional information

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

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.

Brute Force

Intuition

The most direct way to solve this is to check the sum of every single possible subarray.

We can set a starting index i, and then use a second pointer j to expand the subarray to the right. As we expand, we keep a running total of the current subarray's sum. If this running total ever exceeds our recorded maximum sum, we update our maximum. We repeat this process for every possible starting index in the array.

Algorithm

1. Initialize max_sum to negative infinity (float('-inf')) to ensure any valid subarray sum will overwrite it.
2. Loop i from 0 to the length of nums. This represents the start of our subarray.
3. Initialize current_sum = 0 for the new starting point.
4. Loop j from i to the length of nums. This represents the end of our subarray.
5. Add nums[j] to current_sum.
6. Update max_sum = max(max_sum, current_sum).
7. Return max_sum after all combinations are checked.

def max_sub_array(nums: list[int]) -> int:
    max_sum = float('-inf')
    
    for i in range(len(nums)):
        current_sum = 0
        for j in range(i, len(nums)):
            current_sum += nums[j]
            max_sum = max(max_sum, current_sum)
            
    return max_sum

Time & Space Complexity

• Time complexity: O(N^2)

• Reason: We use a nested loop to evaluate every possible contiguous subarray. Given the constraint of 10^5 elements, this will trigger a Time Limit Exceeded (TLE) error.

• Space complexity: O(1)

• Reason: We only use a couple of integer variables to track the sums, requiring no extra memory.

Kadane's Algorithm - Optimal

Intuition

We can solve this in a single pass using Kadane's Algorithm, which is a brilliant application of Greedy/Dynamic Programming concepts.

As we iterate through the array, we maintain a running current_sum. The core realization is this: a negative prefix sum will always drag down the total sum of whatever comes next. If our current_sum drops below zero, it has become a liability. Instead of carrying that negative baggage forward, we should completely abandon it and start a brand new subarray from the current element!

By simply resetting our current_sum to zero whenever it dips into the negatives, and constantly updating our max_sum, we can find the optimal subarray in O(N) time.

Algorithm

1. Initialize max_sum to the first element of the array (nums[0]).
2. Initialize current_sum to 0.
3. Iterate through every num in nums:

• If current_sum is negative (current_sum < 0), reset it to 0. This drops the negative prefix.
• Add the current num to current_sum.
• Update max_sum to be the maximum of its current value and the new current_sum.

4. Return max_sum.

def max_sub_array(nums: list[int]) -> int:
    max_sum = nums[0]
    current_sum = 0
    
    for num in nums:
        # Drop the previous subarray if its sum is negative
        if current_sum < 0:
            current_sum = 0
            
        current_sum += num
        max_sum = max(max_sum, current_sum)
        
    return max_sum

Time & Space Complexity

• Time complexity: O(N)

• Reason: We iterate through the nums array exactly one time. The operations inside the loop are constant time O(1).

• Space complexity: O(1)

• Reason: We only use two integer variables (max_sum and current_sum) to track the state, completely avoiding any extra arrays.