You are given an array of integers (both positive and negative). Find the continous sequence with the largest sum. Return the sum.
##Example
Input: {2, -8, 3, -2, 4, -10}
Output: 5 (i.e, {3, -2, 4})
##Powerd by CodeWarrior
You are given an array of integers (both positive and negative). Find the continous sequence with the largest sum. Return the sum.
##Example
Input: {2, -8, 3, -2, 4, -10}
Output: 5 (i.e, {3, -2, 4})
##Powerd by CodeWarrior
module.exports = function (seq) { | |
var maxsum = -1000000000; | |
var sum = 0; | |
for (var i = 0; i < seq.length; i++) { | |
sum += seq[i]; | |
if(sum > maxsum) { | |
maxsum = sum; | |
} | |
if (sum < 0) { | |
sum = 0; | |
}; | |
}; | |
return maxsum; | |
} |
{ | |
"id": 9, | |
"name": "continous sequence sum", | |
"level": "basic", | |
"author": "CareerCup" | |
} |
var func = require("./"); | |
var expect = require("expect.js") | |
describe("func", function () { | |
it("should return largest sum in sequence", function() { | |
expect(func([2, -8, 3, -2, 4, -10])).to.equal(5); | |
expect(func([2, -8, 3, -2, 4, -10, 12, 15, -14, -100, 1, 5])).to.equal(27); | |
}); | |
it("should return largest sum in all minus sequence", function() { | |
expect(func([-10, -8, -3, -2, -4, -10])).to.equal(-2); | |
}); | |
it("should return large sequence", function() { | |
var seq = [] | |
for (var i = 0; i < 100000; i++) { | |
seq.push(i); | |
}; | |
expect(func(seq)).to.eql(4999950000) | |
}); | |
}); |