38 lines
992 B
Plaintext
38 lines
992 B
Plaintext
/* Greatest Subsequential Sum, in Jsish */
|
|
function sumValues(arr) {
|
|
var result = 0;
|
|
for (var i = 0, len = arr.length; i < len; i++) result += arr[i];
|
|
return result;
|
|
}
|
|
|
|
function greatestSubsequentialSum(population:array):array {
|
|
var maxValue = (population[0]) ? population[0] : 0;
|
|
var subsequence = [], greatest = [];
|
|
|
|
for (var i = 0, len = population.length; i < len; i++) {
|
|
for (var j = i; j < len; j++) {
|
|
subsequence = population.slice(i, j);
|
|
var value = sumValues(subsequence);
|
|
if (value > maxValue) {
|
|
maxValue = value;
|
|
greatest = subsequence;
|
|
};
|
|
}
|
|
}
|
|
|
|
return [maxValue, greatest];
|
|
}
|
|
|
|
if (Interp.conf('unitTest')) {
|
|
var gss = [-1,-2,3,5,6,-2,-1,4,-4,2,-1];
|
|
; gss;
|
|
; greatestSubsequentialSum(gss);
|
|
}
|
|
|
|
/*
|
|
=!EXPECTSTART!=
|
|
gss ==> [ -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1 ]
|
|
greatestSubsequentialSum(gss) ==> [ 15, [ 3, 5, 6, -2, -1, 4 ] ]
|
|
=!EXPECTEND!=
|
|
*/
|