Here, We see Maximum Subarray LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Maximum Subarray LeetCode Solution
Table of Contents
Problem Statement
Given an integer array nums
, find the
subarray which has the largest sum and return its sum.
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
Maximum Subarray Leetcode Solution C++
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max_sum=INT_MIN, curr_sum=0;
for(int i=0;i<nums.size();i++){
curr_sum+=nums[i];
if(curr_sum>max_sum)
max_sum=curr_sum;
if(curr_sum<0)
curr_sum=0;
}
return max_sum;
}
};
Code language: HTML, XML (xml)
Maximum Subarray Leetcode Solution Java
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int max = Integer.MIN_VALUE, sum = 0;
for(int i=0;i<n;i++){
sum += nums[i];
max = Math.max(sum,max);
if(sum<0) sum = 0;
}
return max;
}
}
Code language: JavaScript (javascript)
Maximum Subarray Leetcode Solution JavaScript
var maxSubArray = function(nums) {
var prev = 0;
var max = -Number.MAX_VALUE;
for (var i = 0; i < nums.length; i++) {
prev = Math.max(prev + nums[i], nums[i]);
max = Math.max(max, prev);
}
return max;
};
Code language: JavaScript (javascript)
Maximum Subarray Solution Python
class Solution(object):
def maxSubArray(self, nums):
if not nums:
return 0
curSum = maxSum = nums[0]
for num in nums[1:]:
curSum = max(num, curSum + num)
maxSum = max(maxSum, curSum)
return maxSum