# Maximum Subarray Problem Solution

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.```

## 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;
}``````