Sunday, 19 August 2018

find max sub array program

Program1: find sum of maxSubArray

 public int maxSubArray(final int[] A) {
     int largestSum = Integer.MIN_VALUE;
        int tempSum = 0;
        for(int i=0;i<A.length;i++) {
            if(tempSum+A[i]<A[i]) {
                tempSum = A[i];
            }else {
                tempSum = tempSum+A[i];
            }
           
            if((tempSum>Integer.MIN_VALUE && tempSum>largestSum) || tempSum>0) {
                 if(largestSum<tempSum){
                    largestSum = tempSum;
                
                    }
            }else {
                tempSum=0;
            }
        }
        return largestSum;
    }


intput:{-2,1,-3,-4,-1,-2,-1,-7,-5,-4}

output: 1


innput:{-160,-20,-10}
output -10

input: -160,-20,-10,1,2
output: 3



Program2: find sum of maxSubArray with start and end index

public static void findMaxSumSubArray(int[] arr) {
        int largestSum = Integer.MIN_VALUE;
        int tempSum = 0;
        int startIndex = 0;
        int endIndex = 0;
        int s = 0;
        for(int i=0;i<arr.length;i++) {
            if(tempSum+arr[i]<arr[i]) {
                tempSum = arr[i];
            }else {
                tempSum = tempSum+arr[i];
            }
           
            if((tempSum>Integer.MIN_VALUE && tempSum>largestSum) || tempSum>0) {
                 if(largestSum<tempSum){
                     endIndex = i;
                     startIndex = s;
                    largestSum = tempSum;
               
                    }
            }else {
                s = i+1;
                tempSum=0;
            }
        }
        System.out.println("index start::"+startIndex +" and end: "+endIndex);
        System.out.println("sum::"+largestSum);
    }


No comments:

Post a Comment

links for Data Structure

  1) 𝐁𝐞𝐜𝐨𝐦𝐞 𝐌𝐚𝐬𝐭𝐞𝐫 𝐢𝐧 𝐋𝐢𝐧𝐤𝐞𝐝 𝐋𝐢𝐬𝐭:  https://lnkd.in/gXQux4zj 2) 𝐀𝐥𝐥 𝐭𝐲𝐩𝐞𝐬 𝐨𝐟 𝐓𝐫𝐞𝐞 𝐓𝐫𝐚𝐯𝐞𝐫𝐬𝐚𝐥𝐬...