Maximum Subarray Sum (Kadane's)

Hard Arrays

Find the largest sum of any contiguous subarray using Kadane's algorithm.

Sample input

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

Sample output

Solution

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
best = current = arr[0]
for x in arr[1:]:
    current = max(x, current + x)
    best = max(best, current)
print(best)

const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
let best = arr[0], current = arr[0];
for (let i = 1; i < arr.length; i++) {
  current = Math.max(arr[i], current + arr[i]);
  best = Math.max(best, current);
}
console.log(best);

public class Main {
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int best = arr[0], current = arr[0];
        for (int i = 1; i < arr.length; i++) {
            current = Math.max(arr[i], current + arr[i]);
            best = Math.max(best, current);
        }
        System.out.println(best);
    }
}

fun main() {
    val arr = intArrayOf(-2, 1, -3, 4, -1, 2, 1, -5, 4)
    var best = arr[0]
    var current = arr[0]
    for (i in 1 until arr.size) {
        current = maxOf(arr[i], current + arr[i])
        best = maxOf(best, current)
    }
    println(best)
}

let arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
var best = arr[0], current = arr[0]
for i in 1..<arr.count {
    current = max(arr[i], current + arr[i])
    best = max(best, current)
}
print(best)

import 'dart:math';

void main() {
  List<int> arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
  int best = arr[0], current = arr[0];
  for (int i = 1; i < arr.length; i++) {
    current = max(arr[i], current + arr[i]);
    best = max(best, current);
  }
  print(best);
}

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

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = 9;
    int best = arr[0], current = arr[0];
    for (int i = 1; i < n; i++) {
        current = max(arr[i], current + arr[i]);
        best = max(best, current);
    }
    cout << best << endl;
    return 0;
}

#include <stdio.h>

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = 9;
    int best = arr[0], current = arr[0];
    for (int i = 1; i < n; i++) {
        int add = current + arr[i];
        current = arr[i] > add ? arr[i] : add;
        best = best > current ? best : current;
    }
    printf("%d\n", best);
    return 0;
}