In this guide, you will get 53. Maximum Subarray LeetCode Solution with the best time and space complexity. The solution to Maximum Subarray problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
53. Maximum Subarray LeetCode Solution in C++
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// dp[i] := the maximum sum subarray ending in i
vector<int> dp(nums.size());
dp[0] = nums[0];
for (int i = 1; i < nums.size(); ++i)
dp[i] = max(nums[i], dp[i - 1] + nums[i]);
return ranges::max(dp);
}
}; /* code provided by PROGIEZ */
53. Maximum Subarray LeetCode Solution in Java
class Solution {
public int maxSubArray(int[] nums) {
// dp[i] := the maximum sum subarray ending in i
int[] dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1; i < nums.length; ++i)
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
return Arrays.stream(dp).max().getAsInt();
}
} // code provided by PROGIEZ
53. Maximum Subarray LeetCode Solution in Python
class Solution:
def maxSubArray(self, nums: list[int]) -> int:
# dp[i] := the maximum sum subarray ending in i
dp = [0] * len(nums)
dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = max(nums[i], dp[i - 1] + nums[i])
return max(dp) # code by PROGIEZ
