Largest Sum Subarray

editor-page-cover

Problem Statement

In the array below, the largest sum subarray starts at index 3 and ends at 6, and with the largest sum being 12.

widget

Hint

  • Use Kadane’s algorithm

Try it yourself

int find_max_sum_sub_array(int A[], int n) {
  //TODO: Write - Your - Code
  return -1;
}

Solution

int find_max_sum_sub_array(int A[], int n) {
  if (n < 1) {
    return 0;
  }
  
  int curr_max = A[0];
  int global_max = A[0];
  for (int i = 1; i < n; ++i) {
    if (curr_max < 0) {
      curr_max = A[i];
    } else {
      curr_max += A[i];
    }

    if (global_max < curr_max) {
      global_max = curr_max;
    }
  }

  return global_max;
}

int main() {
    
    int v[] = {-4, 2, -5, 1, 2, 3, 6, -5, 1};
    cout << "Sum of largest subarray: " << find_max_sum_sub_array(v, sizeof(v) / sizeof(v[0])) << endl;
    return 0;
  }

Solution Explanation

Runtime complexity

The runtime complexity of this solution is linear, O(n).

Memory complexity

The memory complexity of this solution is constant, O(1).

The basic idea of Kadane’s algorithm is to scan the entire array and at each position find the maximum sum of the subarray ending there. This is achieved by keeping a current_max for the current array index and a global_max. The algorithm is as follows:

current_max = A[0]
global_max = A[0]
for i = 1 -> size of A
    if current_max is less than 0
        then current_max = A[i]
    otherwise 
        current_max = current_max + A[i]
    if global_max is less than current_max 
        then global_max = current_max