Solution: Maximum Subarray

Given an integer array, nums, find the contiguous subarray that has the largest sum and return its sum.

Note: A subarray is a contiguous part of an array that contains at least one number.

Constraints:

• $1 \leq$ nums.length $\leq 10^5$

• $-10^4 \leq$ nums[i] $\leq 10^4$

We’ll solve this problem using Kadane’s Algorithm. It’s a dynamic programming approach. The key idea is that we can efficiently find the maximum subarray ending at any position based on the maximum subarray ending at the previous position.

The subproblem here is finding the maximum subarray sum that ends at a specific index i. We need to calculate this for every index i in the array. The base case is the first element of the array, where both current subarray sum and maximum subarray sum are initialized with the first element’s value. This is the starting point for solving the subproblems. At each step, we reuse the previously computed maximum subarray sum to find the solution for the current subproblem.

The steps of the algorithm are given below:

1. Initialize two variables, current_sum and max_sum, with the value of the first element in the input list. These variables are used to keep track of the current sum of the subarray being considered, and the maximum sum found so far.

2. Iterate through the input list, starting from the second element to the end of the list. Within the loop, perform the following steps:

   • If current_sum + nums[i] is smaller than nums[i], this indicates that starting a new subarray with nums[i] would yield a larger sum than extending the previous subarray. In such cases, reset current_sum to nums[i].

   • Compare the current max_sum with the updated current_sum. This step ensures that the max_sum always stores the maximum sum encountered so far.

3. After the loop completes, the function returns the max_sum, which represents the maximum sum of any contiguous subarray within the input list.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s implement the algorithm as discussed above:

The time complexity of this solution is $O(n)$, because we are iterating the array once, where $n$ is the total number of elements in the array.

The space complexity of this solution is $O(1)$.