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

Post a Comment

Popular posts from this blog

Rearrange Array in Maximum-Minimum form

Given a sorted array of positive integers, rearrange the array alternately i.e first element should be the maximum value, second minimum value, third-second max, fourth-second min and so on. Naive Solution: Here we will use an auxiliary array to store the elements in correct order. For even indices of the array  Large numbers from the given array are added. For odd indices small numbers are added. Code: import java.util.*; public class Test{        public static void main(String[] args) {          Scanner in = new Scanner(System.in);     int[] a = {1,2,3,4,5,6,7,8,9};     int n = a.length;     int[] temp = new int[n];     int small = 0;     int large = n-1;     for(int i=0; i<n; i++){         if(i%2 == 0){             temp[i] = a[large--];         }  ...
Read more

Write a progtam to calculate size of a tree

Recursion Steps:   Size of a tree= 1+size of left subtree + size of right subtree   Base case : return zero if  a node is null Code:     Time:O(n) class Node{     int data;     Node left, right;     Node(int data){         this.data = data;     } } public class SizeOfBinaryTree {       static int calculateSize(Node node){           if(node == null){               return 0;           }                     return (1+calculateSize(node.left)+calculateSize(node.right));       }             public static void main(String[] args){      ...
Read more