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.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1] Output: 1
Example 3:
Input: nums = [5,4,-1,7,8] Output: 23
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
Maximum Subarray Solutions
✅Time: O(n)
✅Space: O(1)
C++
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = INT_MIN;
int sum = 0;
for (const int num : nums) {
sum += num;
ans = max(ans, sum);
sum = max(sum, 0);
}
return ans;
}
};
Java
class Solution {
public int maxSubArray(int[] nums) {
int ans = Integer.MIN_VALUE;
int sum = 0;
for (final int num : nums) {
sum += num;
ans = Math.max(ans, sum);
sum = Math.max(sum, 0);
}
return ans;
}
}
Python
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
ans = -math.inf
summ = 0
for num in nums:
summ += num
ans = max(ans, summ)
summ = max(summ, 0)
return ans
Watch Tutorial
Checkout more Solutions here