import 'package:test/test.dart';

import 'dart:math';

int kadanesAlgorithm(List<int> array) {

int maxEndingHere = array[0];

int maxSoFar = array[0];

for (int num in array.sublist(1, array.length)) {

maxEndingHere = max(maxEndingHere + num, num);

maxSoFar = max(maxSoFar, maxEndingHere);

}

return maxSoFar;

}

void main() {

List<int> array;

int maxContiniousSubarraySum;

test(('.Check the response for each test case'), () {

array = [3, 5, -9, 1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1, -5, 4];

maxContiniousSubarraySum = kadanesAlgorithm(array);

expect(maxContiniousSubarraySum, equals(19));

});

test(('.Check the response for each test case'), () {

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

maxContiniousSubarraySum = kadanesAlgorithm(array);

expect(maxContiniousSubarraySum, equals(55));

});

test(('.Check the response for each test case'), () {

array = [-1, -2, -3, -4, -5, -6, -7, -8, -9, -10];

maxContiniousSubarraySum = kadanesAlgorithm(array);

expect(maxContiniousSubarraySum, equals(-1));

});

test(('.Check the response for each test case'), () {

array = [1, 2, 3, 4, 5, 6, -22, 7, 8, 9, 10];

maxContiniousSubarraySum = kadanesAlgorithm(array);

expect(maxContiniousSubarraySum, equals(34));

});

}