Data Structures and Algos problem-5

Question (Asked in Google)

Find the max from the contiguous  sub arrays if the integer array is [-2,2,5,-11,6] .

answer : 7

Answer

Lets understand first what the question means?

the Contiguous sub array means we can take the sub array as lets say [-2,2] or say [2,5] means all the possible array out of the given array

So lets say 

• [-2,2] i.e -2+2=0
• [2,5] i.e 2+5 =7    this is the answer
• [5-11] i.e 5+-11= -6
• [-11,6] i.e -5

like wise we can take [-2,2,5] i.e 5 but the number must be contiguous i.e we cant take [2,6,5] that's not allowed

So lets move on to the solution

int [] array= {-2,2,5,-11,6};
      int max_sum=array[0];    //i.e -2
      int current_sum=max_sum;  //i.e -2
      for(int i=1;i<array.length;i++) { // we count from index 1 that is from 2
          current_sum  = Math.max(array[i]+current_sum, array[i]);  //i.e 2 + -2=0,2 (we start looping from 1)
          max_sum=Math.max(current_sum, max_sum); //i.e (0,2) so obviosuly 2 
      }
      System.out.println(max_sum);
    }

lets dry run it

for the first time 2 will be the max_sum out of [-2 and 2] we compare -2+2 or 2

Now we get 5 in the condition so 

we need to choose from 5+2 or 5 that is obviously 5+2=7 

so max is 7

now comes -11

so will check as -11+7 or -11 so we get -4 is greater but check the second line inside the for loop so we need to choose the max again out of -4 and 7 that is max will remain to 7

then comes the 6

So now the current sum is -4  so 6+-4 or 6

the answer is 6 now the second line 6 or 7 that is max of current sum or max sum so 7 is the max which is the answer..!!