Kadane's Algorithm

• Used to find the maximum sum of a subarray in O(n) time.

Python

# Kadane's algorithm to find the maximum sum substring in a string of digits
 
arr = [1,2,-8, 7,-1, 2, 3]
 
max_sum = 0
maxEnding = arr[0]
 
for i in range(len(arr)):
    maxEnding = max(maxEnding+arr[i], arr[i])
    max_sum = max(max_sum, maxEnding)
 
 
print(max_sum)

CPP

#include <iostream>
 
using namespace std;
 
int main() {
  int arr[] = {1, 2, -8, 7, -1, 2, 3};
  int maxEnding = arr[0];
  int max_sum = 0;
 
  for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {
    maxEnding = max(maxEnding + arr[i], arr[i]);
    max_sum = max(max_sum, maxEnding);
  }
  cout << max_sum;
}