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.

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