# Maximum Subarray **Difficulty:** MEDIUM [External](https://leetcode.com/problems/maximum-subarray) Canonical: https://scaleengineer.com/dsa/problems/maximum-subarray **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming) **Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer) **Data structures:** Array **Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Atlassian](https://scaleengineer.com/companies/atlassian), [Barclays](https://scaleengineer.com/companies/barclays), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cisco](https://scaleengineer.com/companies/cisco), [Cognizant](https://scaleengineer.com/companies/cognizant), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Huawei](https://scaleengineer.com/companies/huawei), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [SAP](https://scaleengineer.com/companies/sap), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Tekion](https://scaleengineer.com/companies/tekion), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [persistent systems](https://scaleengineer.com/companies/persistent-systems), [tcs](https://scaleengineer.com/companies/tcs), [Nike](https://scaleengineer.com/companies/nike), [Optum](https://scaleengineer.com/companies/optum), [PornHub](https://scaleengineer.com/companies/pornhub), [Tesla](https://scaleengineer.com/companies/tesla), [Turing](https://scaleengineer.com/companies/turing), [Autodesk](https://scaleengineer.com/companies/autodesk), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Rippling](https://scaleengineer.com/companies/rippling), [Snap](https://scaleengineer.com/companies/snap), [HashedIn](https://scaleengineer.com/companies/hashedin), [Vimeo](https://scaleengineer.com/companies/vimeo), [Zomato](https://scaleengineer.com/companies/zomato), [Upstart](https://scaleengineer.com/companies/upstart), [Ripple](https://scaleengineer.com/companies/ripple), [Target](https://scaleengineer.com/companies/target) --- ## Problem Given an integer array `nums`, find the subarray with 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. **Constraints:** * `1 <= nums.length <= 105` * `-104 <= nums[i] <= 104` **Follow up:** If you have figured out the `O(n)` solution, try coding another solution using the **divide and conquer** approach, which is more subtle. # Approaches ## Brute Force The brute-force approach is the most straightforward way to solve the problem. It involves generating every possible contiguous subarray, calculating the sum of each, and keeping track of the maximum sum found. This method guarantees finding the correct answer by exhaustively checking all possibilities. **Time:** O(n^2) · **Space:** O(1) **Pros:** Simple to understand and implement.; Correctness is easy to verify. **Cons:** Very inefficient for large arrays.; Will likely result in a 'Time Limit Exceeded' (TLE) error on most online coding platforms for the given constraints. ### Explanation This method considers every possible subarray. We can define a subarray by its start and end indices. We use two nested loops to iterate through all possible start and end points. The outer loop selects the starting index `i`, and the inner loop selects the ending index `j`. For each pair of `(i, j)`, we calculate the sum of the elements in `nums` from index `i` to `j`. We maintain a global variable, `maxSum`, initialized to a very small number (like `Integer.MIN_VALUE`). As we calculate the sum of each subarray, we compare it with `maxSum` and update `maxSum` if the current subarray's sum is larger. An optimization to the naive three-loop approach is to calculate the sum iteratively in the second loop. As `j` increments, we just add `nums[j]` to the sum of the subarray `nums[i...j-1]`. This reduces the complexity from O(n³) to O(n²). ```java class Solution { public int maxSubArray(int[] nums) { int n = nums.length; int maxSum = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { int currentSum = 0; for (int j = i; j < n; j++) { // Add the current element to the subarray sum currentSum += nums[j]; // Update maxSum if the current subarray sum is greater if (currentSum > maxSum) { maxSum = currentSum; } } } return maxSum; } } ``` ### Algorithm - Initialize a variable `maxSum` to the smallest possible integer value. - Use a nested loop structure. The outer loop, with index `i`, iterates from the start to the end of the array, fixing the starting element of a subarray. - The inner loop, with index `j`, iterates from `i` to the end of the array, fixing the ending element of a subarray. - For each subarray defined by `i` and `j`, calculate its sum. A third loop can be used, or more efficiently, a `currentSum` variable can be updated within the second loop. - Compare the `currentSum` of each subarray with `maxSum`. If `currentSum` is greater, update `maxSum`. - After iterating through all possible subarrays, `maxSum` will hold the maximum subarray sum. ## Divide and Conquer This approach uses the divide and conquer paradigm, which is a powerful algorithmic technique. The problem is broken down into smaller, independent subproblems. The maximum subarray for a given array `A[L...R]` can lie in one of three places: 1. Entirely in the left subarray `A[L...mid]`. 2. Entirely in the right subarray `A[mid+1...R]`. 3. In a subarray that crosses the midpoint `mid`. The first two are solved recursively. The third case is solved by finding the maximum subarray that ends at `mid` and the maximum subarray that starts at `mid+1` and combining them. The final answer is the maximum of these three results. **Time:** O(n log n) · **Space:** O(log n) **Pros:** A good demonstration of the divide and conquer technique.; More efficient than the brute-force approach. **Cons:** More complex to implement compared to other approaches.; Less efficient than the linear-time Kadane's algorithm. ### Explanation The divide and conquer strategy involves splitting the array into two halves and solving the problem recursively for each half. The crucial part is the 'combine' step, where we consider the case that the maximum subarray spans across the midpoint. Let's define a function `findMax(nums, left, right)`: 1. If `left == right`, we have a single-element array, so we return `nums[left]`. 2. Otherwise, we find the midpoint `mid = (left + right) / 2`. 3. The result is the maximum of: a. `findMax(nums, left, mid)`: The max subarray sum in the left half. b. `findMax(nums, mid + 1, right)`: The max subarray sum in the right half. c. `findCrossingSum(nums, left, mid, right)`: The max subarray sum that crosses the midpoint. To find the crossing sum, we iterate from `mid` down to `left` to find the largest possible sum for the left part of the crossing subarray. Then, we iterate from `mid + 1` up to `right` to find the largest sum for the right part. The sum of these two parts gives the maximum crossing subarray sum. ```java class Solution { public int maxSubArray(int[] nums) { return findMaxSubArray(nums, 0, nums.length - 1); } private int findMaxSubArray(int[] nums, int left, int right) { // Base case: only one element if (left == right) { return nums[left]; } int mid = left + (right - left) / 2; // 1. Max subarray sum in left half int leftSum = findMaxSubArray(nums, left, mid); // 2. Max subarray sum in right half int rightSum = findMaxSubArray(nums, mid + 1, right); // 3. Max subarray sum crossing the midpoint int crossSum = findMaxCrossingSubArray(nums, left, mid, right); // Return the maximum of the three return Math.max(Math.max(leftSum, rightSum), crossSum); } private int findMaxCrossingSubArray(int[] nums, int left, int mid, int right) { int leftSum = Integer.MIN_VALUE; int currentSum = 0; for (int i = mid; i >= left; i--) { currentSum += nums[i]; if (currentSum > leftSum) { leftSum = currentSum; } } int rightSum = Integer.MIN_VALUE; currentSum = 0; for (int i = mid + 1; i <= right; i++) { currentSum += nums[i]; if (currentSum > rightSum) { rightSum = currentSum; } } return leftSum + rightSum; } } ``` ### Algorithm - Define a recursive function that takes the array and the `left` and `right` indices as input. - **Base Case:** If `left` equals `right`, there is only one element, so return that element's value. - **Divide:** Find the middle index `mid` of the current segment. - **Conquer:** 1. Recursively find the maximum subarray sum for the left half (`left` to `mid`). 2. Recursively find the maximum subarray sum for the right half (`mid + 1` to `right`). 3. Find the maximum subarray sum that crosses the midpoint. This involves finding the maximum sum of a subarray starting at `mid` and extending to the left, and the maximum sum of a subarray starting at `mid + 1` and extending to the right. The sum of these two is the crossing sum. - **Combine:** Return the maximum of the three sums calculated in the conquer step. ## Kadane's Algorithm (Dynamic Programming) Kadane's algorithm is a dynamic programming approach that solves this problem in linear time. It's remarkably efficient and elegant. The main idea is to scan through the array while keeping track of the maximum sum of a subarray ending at the current position (`currentMax`) and the overall maximum sum found so far (`globalMax`). **Time:** O(n) · **Space:** O(1) **Pros:** Extremely efficient with O(n) time complexity.; Uses constant extra space, O(1).; Simple and concise to implement once the idea is understood. **Cons:** The logic might be slightly less intuitive to grasp initially compared to the brute-force method. ### Explanation This algorithm iterates through the array just once. It maintains a variable `currentMax` which, at each position `i`, stores the maximum possible sum of a subarray that ends at `i`. This subarray is either just the element `nums[i]` itself or the element `nums[i]` appended to the maximum subarray ending at the previous position `i-1`. Thus, the recurrence relation is: `currentMax(i) = max(nums[i], currentMax(i-1) + nums[i])` We also need another variable, `globalMax`, to store the maximum sum found over all positions. At each step, after calculating `currentMax(i)`, we update `globalMax` with `max(globalMax, currentMax(i))`. This ensures we keep track of the overall maximum, as the maximum subarray might not end at the last element of the array. ```java class Solution { public int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) { // As per constraints, nums.length >= 1, but good practice. return 0; } int globalMax = nums[0]; int currentMax = nums[0]; for (int i = 1; i < nums.length; i++) { // Decide whether to extend the previous subarray or start a new one. currentMax = Math.max(nums[i], currentMax + nums[i]); // Update the overall maximum sum found so far. if (currentMax > globalMax) { globalMax = currentMax; } } return globalMax; } } ``` ### Algorithm - Initialize two integer variables: `globalMax` and `currentMax`, both to the value of the first element in the array. - Iterate through the array starting from the second element (`i = 1`). - In each iteration, update `currentMax`. The new `currentMax` is the maximum of the current element `nums[i]` or the sum of `currentMax` and `nums[i]`. This step decides whether to extend the existing subarray or start a new one. - After updating `currentMax`, compare it with `globalMax` and update `globalMax` if `currentMax` is larger. - After the loop finishes, `globalMax` will contain the largest subarray sum. # Solutions ### CSharp ```csharp public class Solution { public int MaxSubArray(int[] nums) { int ans = nums[0], f = nums[0]; for (int i = 1; i < nums.Length; ++i) { f = Math.Max(f, 0) + nums[i]; ans = Math.Max(ans, f); } return ans; } } ``` ### Java ```java class Solution { public int maxSubArray ( int [] nums ) { int ans = nums [ 0 ]; for ( int i = 1 , f = nums [ 0 ]; i < nums . length ; ++ i ) { f = Math . max ( f , 0 ) + nums [ i ]; ans = Math . max ( ans , f ); } return ans ; } } ``` ### JavaScript ```javascript /** * @param {number[]} nums * @return {number} */ var maxSubArray = function ( nums, ) { let [ans, f] = [nums[0], nums[0]]; for (let i = 1; i < nums.length; ++i) { f = Math.max(f, 0) + nums[i]; ans = Math.max(ans, f); } return ans; }; ``` ### CPP ```cpp class Solution { public: int maxSubArray ( vector < int >& nums ) { int ans = nums [ 0 ], f = nums [ 0 ]; for ( int i = 1 ; i < nums . size (); ++ i ) { f = max ( f , 0 ) + nums [ i ]; ans = max ( ans , f ); } return ans ; } }; ``` ### Python ```python class Solution : def maxSubArray ( self , nums : List [ int ]) -> int : res = cur_sum = nums [ 0 ] for num in nums [ 1 :]: cur_sum = num + max ( cur_sum , 0 ) res = max ( res , cur_sum ) return res ```