The Interview Question Today#7(2-3-19)

Question:

The algorithm to find the contiguous sub-array with the maximum sum, for a given array of positive and negative numbers. (Kadane’s Algorithm)

Example:

Input: Array= {-2, -5, 6, -2, -3, 1, 5, -6}

Output: The maximum subarray sum is 7 

Solution:

Approach:
Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
        
return max_so_far
C Program:
#include<stdio.h>

// Function to find contiguous sub-array with the largest sum
// in given set of integers
int kadane(int arr[], int n)
{

int max_so_far = 0;

int max_ending_here = 0;
int i;
for ( i = 0; i < n; i++)
{

max_ending_here = max_ending_here + arr[i];
 if(max_ending_here>0){
max_ending_here =max_ending_here;
 }
 else{
    max_ending_here=0;
 }
 if(max_so_far<max_ending_here)
{
    max_so_far=max_ending_here;
}
}
return max_so_far;
}

int main()
{
int arr[100],n,i;
printf("Enter the number elements u wanted insert");
scanf("%d",&n);
printf("Enter the elements\n");
for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
}

printf("The sum of contiguous sub-array with the largest sum is %d",kadane(arr, n));

return 0;
}
Output:
Enter the number elements u wanted insert5
Enter the elements
-2
-1
6
4
-3
The sum of contiguous sub-array with the largest sum is 10