Largest Contiguous Sum Editorial

Practice Problem Link: Largest Contiguous Sum | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array (may contain also negative elements), return the largest contiguous sum from the array.

Naive Approach

We can iterate over all possible subarrays of the array and calculate their sum. Then return the maximum possible value of the sum obtained.

Analysis

• Time Complexity: O(n³)
• Space Complexity: O(1)

Implementation

C++

int largestContiguousSum(vector <int> &arr){
   int maxSubarraySum = INT_MIN;
       for(int i = 0; i < arr.size(); i++) {
           for(int j = 0; j < arr.size(); j++) {
               int subarraySum = 0;
               for(int k = i; k <= j; k++) {
                   subarraySum += arr[k];
               }
               maxSubarraySum = max(maxSubarraySum, subarraySum);
           }
   }
   return maxSubarraySum;
}

Java

class Solution {
   int largestContiguousSum(int[] arr){
       int maxSubarraySum = Integer.MIN_VALUE;
       for(int i = 0; i < arr.length; i++) {
           for(int j = 0; j < arr.length; j++) {
               int subarraySum = 0;
               for(int k = i; k <= j; k++) {
                   subarraySum += arr[k];
               }
               maxSubarraySum = Math.max(maxSubarraySum, subarraySum);
           }
       }
       return maxSubarraySum;
   }
}

Kadane's Algorithm

The largest contiguous sum can be solved optimally using Kadane's Algorithm in linear time. The key idea in Kadane's Algorithm is to keep track of all positive contiguous subarrays of the array and keep track of the maximum sum encountered yet and keep updating the maximum sum encountered. An edge case will be when all elements are negative, which has to be handled separately.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

int largestContiguousSum(vector <int> &arr){
   int maximumSum = 0, currentSum = 0;
   int maxValue = INT_MIN, minValue = INT_MAX;
   for (int x: arr) {
       maxValue = max(maxValue, x);
       minValue = min(minValue, x);
   }
   if(maxValue < 0) {
       return minValue;
   }
   for (int i = 0; i < arr.size(); i++) {
       currentSum += arr[i];
       maximumSum = max(maximumSum, currentSum);
       if(currentSum < 0) {
           currentSum = 0;
       }
   }
   return maximumSum;
}

Java

class Solution {
   int largestContiguousSum(int[] arr){
       int maximumSum = 0, currentSum = 0;
       int maxValue = Integer.MIN_VALUE;
       int minValue = Integer.MAX_VALUE;
       for(int i = 0; i < arr.length; i++) {
           maxValue = Math.max(maxValue, arr[i]);
           minValue = Math.min(minValue, arr[i]);
       }
       if(maxValue < 0) {
           return minValue;
       }
       for (int i = 0; i < arr.length; i++) {
           currentSum += arr[i];
           maximumSum = Math.max(maximumSum, currentSum);
           if(currentSum < 0) {
               currentSum = 0;
           }
       }
       return maximumSum;
   }
}