Amazon Coding Interview Question - Find The Sum Of Contiguous SubArray with Largest Sum

Problem Statement

Find The Sum Of Contiguous SubArray with Largest Sum

Description - for a given array lots of subarrays are possible but we have to find a sub-array which gives us the largest sum

arr = [-2,-3,4,-1,-2,1,5,-3]

In this particular array arr, subarray [4,-1,-2,1,5] gives us the maximum sum 7 out of all the subarrays possible.

Expected Output : 7
The above sum is the sum of the subArray [4,-1,-2,1,5]

Efficient Implementation

Time Complexity - O(n) // as we are traversing the array only once where n is the size of the array
Space Complexity - O(1) // as we are just using two variables maxSum and curSum

C++ Implemention

#include<iostream> 
#include<climits> 
using namespace std; 

int findSubArrayMaxSum(int a[],int n){

  // currSum keeps track of the sum of the current subArray
  // maxSum keeps track of the maximum sum that has occurred till then
  // intially both will be 0 and as I traverse through the array these variables
  // will get changed
  int maxSum = 0,currSum = 0;
  for(int i=0;i<n;i++){
    // Calculate the current sum
    currSum+=a[i];
    // if the current sum changes to a negative value I will set it back to 0
    // that way I can keep track of the maximum sum
    if(currSum <0){
      currSum = 0;
    } else if(maxSum < currSum){
      // assign currSum to maxSum  if maxSum is less than currSum and currSum is 
      // greater than 0
      maxSum = currSum;
    }
  }
  return maxSum;
}

int main() 
{ 
    int a[] = {-2, -3, 4, -1, -2, 1, 5, -3}; 
    int n = sizeof(a)/sizeof(a[0]); 
    int max_sum = findSubArrayMaxSum(a, n); 
    cout << "Maximum contiguous sum is " << max_sum; 
    return 0; 
}

If you found this article helpful, please tap the Follow this channel for more articles on data strucures and algorithms.