Back to Greedy
Medium
Maximum Subarray
Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A subarray is a contiguous part of an array.
Examples
Input:nums = [-2,1,-3,4,-1,2,1,-5,4]
Output:6
[4,-1,2,1] has the largest sum = 6.
Input:nums = [1]
Output:1
The subarray [1] has the largest sum 1.
Input:nums = [5,4,-1,7,8]
Output:23
The subarray [5,4,-1,7,8] has the largest sum 23.
Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Kadane's Algorithm (Greedy)
Approach
We iterate through the array and keep a running sum (`currentSum`). If `currentSum` ever becomes negative, it means that the prefix we have accumulated so far will only decrease the sum of any future subarray. Therefore, we should discard the current prefix and reset `currentSum` to 0 (or just to the next number). At each step, we update the global `maxSum` with the maximum of `maxSum` and `currentSum`.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Time complexity is O(n) because we only need a single pass through the array. Space complexity is O(1) as we only use variables for tracking sums.
Solution.java
class Solution { public int maxSubArray(int[] nums) { int maxSum = nums[0]; int currentSum = 0; for (int num : nums) { // If the running sum is negative, discard it if (currentSum < 0) { currentSum = 0; } currentSum += num; maxSum = Math.max(maxSum, currentSum); } return maxSum; }}