Largest sum in contiguous subarray

Given an array find the contiguous subarray with maximum sum:

I) If the array consists of both positive and negative elements:

 We will have the sum initialize the sum to zero. If we find the sum greater then zero then we will update the sum. In successive steps we will update the maximum sum only when it is greater than previous sum.

Code:

import java.util.*;

public class Solution {
    
    public static void main(String[] args) {
        
        int[] a = {-2, -3, 4, -1, -2, 1, 5, -3};
        int n = a.length;
        int sum = 0;
        int newsum = 0;
        for(int i=0; i<n; i++){
            newsum += a[i];
            if(newsum<0){
                newsum = 0;
            }
            else if(newsum>sum){
                sum = newsum;
            }
        }
        System.out.print(sum);
        
       }
}

Output:
7

II) The array may have all elements as negative

    In this method I will initialize current max and max so far to first element. While iterating to other elements I have two options for curr_max, either I can add that element to curr_max, Or I can take that element alone if it curr_max+a[i] is less than a[i]. Then I will compare it with max_so_far and will update if cuur_max is greater than max_so_far.

Code:
import java.util.*;

public class Solution {
    
    public static void main(String[] args) {
        
        int[] a = {-3, -3, -2};
        int size = a.length;
        int max_so_far = a[0];
        int curr_max = a[0];

        for (int i = 1; i < size; i++)
        {
            if(curr_max+a[i]>a[i]){
                curr_max += a[i];
            }
            else{
                curr_max = a[i];
            }
            if(curr_max > max_so_far){
                max_so_far = curr_max;
            }
         }
    
        System.out.print(max_so_far);
        
       }
}

Output:
-2
















Comments

Popular posts from this blog

Rearrange Array in Maximum-Minimum form

Find Maximum in Binary Tree