Maximum Sum Subarray

Chaitra Rai

·

Follow

2 min read

·

Aug 10, 2021

--

Listen

Share

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.(Full Question)

• This can be solved with Kadane’s algorithm
• Kadane’s algorithm is about keeping track of continuous subarray and storing maximum sum until now

public int maxSubArray(int[] nums) {
        int max_subarray_sum_found=0;
        int max_subarray_sum_result=0;
        for(int i=0;i<nums.length;i++){
            max_subarray_sum_found+=nums[i];
            if(max_subarray_sum_found<0)
                max_subarray_sum_found=0;
            if(max_subarray_sum_result<max_subarray_sum_found)
                max_subarray_sum_result=max_subarray_sum_found;
        }
        return max_subarray_sum_result;
    }

• This would take O(1) space complexity and O(n) time complexity
• The algorithm still will not work for negative numbers and we will tweak the conditions a bit and start the result with Integer.MIN_VALUE

public int maxSubArray(int[] nums) {
    int max_subarray_sum_found=0;
    int max_subarray_sum_result=Integer.MIN_VALUE;
    for(int i=0;i<nums.length;i++){
        max_subarray_sum_found=Math.max(nums[i],max_subarray_sum_found+nums[i]);
     max_subarray_sum_result=Math.max(max_subarray_sum_found,max_subarray_sum_result);
   }
    return max_subarray_sum_result;
}

• Space complexity of this would again be O(1)
• We can also use divide and conquer where we can find the sum of the left part of the array and right part of the array and the total sum overall
• one would get the maximum from the left, right or the total left+right
• the other method will be finding if a number itself is greater or the sum

public int maxSubArray(int[] nums) {
    int low=0;
    int high=nums.length-1;
    return maxsubarray(nums,low,high);
}
public int maxsubarray(int[] array,int low,int high){
    if(low==high)
        return array[low];
    int middle=(high+low)/2;
    return Math.max(Math.max(maxsubarray(array,low,middle)
                        ,maxsubarray(array,middle+1,high))
                        ,maxLeftRight(array,low,middle,high));
}
public int maxLeftRight(int[] arr,int low, int middle, int high){        
    int sum=0;
    int left_sum=Integer.MIN_VALUE;
    for(int i=middle;i>=low;i--){
        sum+=arr[i];
        if(sum>left_sum)
            left_sum=sum;
    }
    sum=0;
    int right_sum=Integer.MIN_VALUE;
    for(int i=middle+1;i<=high;i++){
        sum+=arr[i];
        if(sum>right_sum)
            right_sum=sum;
    }
    return Math.max(left_sum+right_sum,Math.max(left_sum,right_sum));
}

• The time complexity would be 2(T/2) for finding maximum subarray of n/2 elements and finding the O(n) on iteration and finding maximum sum
• The time complexity is hence O(nlogn)