Commit857b3be

authored

Merge pull requestmgechev#138 from emyarod/maximum-subarray-linear-time

O(n) Maximum subarray bugfix and tests

2 parents53256ef +1fe106d commit857b3beCopy full SHA for 857b3be

File tree

+33

-5

lines changed

+33

-5

lines changed

Lines changed: 4 additions & 5 deletions

Original file line number	Diff line number	Diff line change
`@@ -20,11 +20,10 @@`
`20`	`20`	`*@return {Number} Maximum sum of the elements of a subarray.`
`21`	`21`	`*/`
`22`	`22`	`functionmaxSubarray(array){`
`23`		`-varcurrentMax=0;`
`24`		`-varmax=0;`
`25`		`-`
`26`		`-for(vari=0;i<array.length;i+=1){`
`27`		`-currentMax=Math.max(0,currentMax+array[i]);`
	`23`	`+varcurrentMax=array[0];`
	`24`	`+varmax=array[0];`
	`25`	`+for(vari=1;i<array.length;i+=1){`
	`26`	`+currentMax=Math.max(array[i],currentMax+array[i]);`
`28`	`27`	`max=Math.max(max,currentMax);`
`29`	`28`	`}`
`30`	`29`	`returnmax;`

Lines changed: 29 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,29 @@`
	`1`	`+varmaxSubArray=require('../../src/searching/maximum-subarray').maxSubarray;`
	`2`	`+`
	`3`	`+describe('Maximum subarray',function(){`
	`4`	`+'use strict';`
	`5`	`+`
	`6`	`+it('should work with empty arrays',function(){`
	`7`	`+expect(maxSubArray([])).toBeUndefined();`
	`8`	`+});`
	`9`	`+`
	`10`	`+it('should return the only element when an array with single element is passed',function(){`
	`11`	`+expect(maxSubArray([42])).toBe(42);`
	`12`	`+});`
	`13`	`+`
	`14`	`+it('should return the only negative element when an array with single element is passed',function(){`
	`15`	`+expect(maxSubArray([-42])).toBe(-42);`
	`16`	`+});`
	`17`	`+`
	`18`	`+it('should return the zero when an array with single element, which is zero is passed',function(){`
	`19`	`+expect(maxSubArray([0])).toBe(0);`
	`20`	`+});`
	`21`	`+`
	`22`	`+it('should return the max sum of a subarray',function(){`
	`23`	`+expect(maxSubArray([1,-1,2,3,-1])).toBe(5);`
	`24`	`+});`
	`25`	`+`
	`26`	`+it('should return the max negative number when array with negative numbers is provided',function(){`
	`27`	`+expect(maxSubArray([-10,-1,-2,-3,-1])).toBe(-1);`
	`28`	`+});`
	`29`	`+});`

Comments

(0)