Write a function that takes in a non-empty array of integers and returns the maximum sum that can be obtained by summing up all of the integers in a non-empty subarray of the input array. A subarray must only contain adjacent numbers (numbers next to each other in the input array).
Sample Input
array = [3, 5, -9, 1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1, -5, 4]
Sample Output
19 // [1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1]
/*function kadanesAlgorithm(array) {
return helper(array, -Infinity, 0, 0)
}
function helper(array, max = -Infinity, current, i) {
if (i > array.length - 1) {
return max
}
const sum = current + array[i];
return helper(array, Math.max(sum, max), sum < 0 ? 0: sum, i + 1);
}*/
function kadanesAlgorithm(array) {
let max = -Infinity;
let current = 0;
for (let num of array) {
current = Math.max(current + num , num)
max = Math.max(current, max)
}
return max
}
// Do not edit the line below.
exports.kadanesAlgorithm = kadanesAlgorithm;
标签:function,Algorithm,max,sum,current,kadanesAlgorithm,Kadane,array From: https://www.cnblogs.com/Answer1215/p/16747389.html