Maximum Subarray Problem: 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 :
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Table of Contents
Maximum Subarray Problem Solution
Problem Solution In Python
solution 1
max_so_far=nums[0]
max_ending_here=0
for i in range(len(nums)):
max_ending_here+=nums[i]
if max_so_far<max_ending_here:
max_so_far=max_ending_here
if max_ending_here<0:
max_ending_here=0
return max_so_far
solution 2
max_so_far=nums[0]
curr_=nums[0]
for i in range(1,len(nums)):
curr_=max(nums[i],curr_+nums[i])
max_so_far=max(max_so_far,curr_)
return max_so_far
Problem Solution In Java
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int currentSum = 0;
for(int i: nums){
currentSum = Math.max(i, currentSum + i);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
Problem Solution In C++
class Solution {
public:
int maxSubArray(vector<int>& nums)
{
int sum=nums[0];
for(int i=1;i<nums.size();i++)
{
int t=nums[i-1]+nums[i];
nums[i]=max(nums[i],t);
sum=max(sum,nums[i]);
}
return sum;
}
};
Problem Solution In C
int maxSubArray(int* nums, int n) {
int ans=nums[0],i,sum=0;
for(i=0;i<n;i++){
sum+=nums[i];
if(ans<sum)ans=sum;
if(sum<0)sum=0;
}
return ans;
}