Maximum Subarray sum

Topic tags :- Array, Divide and ConquerDynamic Programming

Question type :- Easy

Question link : Maximum Subarray

Note : Try yourself before seeing solution here.

Question :

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

Constraints:

1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
 

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.


Solutions : in Java

Solution 1:

class Solution {
    //Using Variable Size Sliding Window
    public int maxSubArray(int[] nums) {
      int result=Integer.MIN_VALUE;
      int tempMax=0;
        
      int i=0;
      int j=0;
        
      while(j<nums.length) {
          tempMax+=nums[j];
          if(tempMax>result){
              result=tempMax;
          }
          
          if(tempMax>=0){
              j++;
          } else{
             tempMax=0;
             j=j+1;
             i=j;
          }
      }  
        
        return result;
    }
}

Runtime: 0 ms
Memory Usage: 38.4 MB
Solution link : click here

Solution 2:

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSoFar=Integer.MIN_VALUE;
        int maxEndingHere=0;
        int n=nums.length;
for(int i=0;i<n;i++) {
            maxEndingHere+=nums[i];
            if(maxEndingHere<nums[i]){
                maxEndingHere=nums[i];
            }
            
            if(maxSoFar<maxEndingHere){
                maxSoFar=maxEndingHere;
            }
}
return maxSoFar;
    }
}

Runtime: 0 ms
Memory Usage: 38.8 MB
Solution link : click here

Solution 3:

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        for(int i=0;i<nums.length;i++){
            int sum =0;
            for(int j=i;j<nums.length;j++){
                sum += nums[j];
                if(sum>max){
                    max = sum;
                }
            }
        }
        return max;
    }
}

Runtime: 139 ms
Memory Usage: 41.5 MB
Solution link : click here

Solution 4:

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int sum =0;
        for(int i=0;i<nums.length;i++){
            
            sum =Math.max(sum+nums[i],nums[i]);
            max = Math.max(max,sum);
        }
        return max;
    }
}

Runtime: 2 ms
Memory Usage: 41.5 MB
Solution link : click here

Thank you

Post a Comment

0 Comments