Merge branch 'master' of github.com:mgechev/javascript-algorithms

mgechev · mgechev · commit 4040286add8e · 2018-05-11T10:54:47.000-07:00
* 'master' of github.com:mgechev/javascript-algorithms:
  minor typo
  Fix O(n) maximum subarray solution
  Add O(n) maximum subarray test
diff --git a/src/data-structures/hash-table.js b/src/data-structures/hash-table.js
@@ -55,7 +55,7 @@
 
   /**
    * Simple non-crypto hash used to hash keys, which determines
-   * while bucket the value will be placed in.
+   * which bucket the value will be placed in.
    * A javascript implementation of Java's 32bitint hash.
    *
    * @public
diff --git a/src/searching/maximum-subarray.js b/src/searching/maximum-subarray.js
@@ -20,11 +20,10 @@
    * @return {Number} Maximum sum of the elements of a subarray.
    */
   function maxSubarray(array) {
-    var currentMax = 0;
-    var max = 0;
-
-    for (var i = 0; i < array.length; i += 1) {
-      currentMax = Math.max(0, currentMax + array[i]);
+    var currentMax = array[0];
+    var max = array[0];
+    for (var i = 1; i < array.length; i += 1) {
+      currentMax = Math.max(array[i], currentMax + array[i]);
       max = Math.max(max, currentMax);
     }
     return max;
diff --git a/test/searching/maximum-subarray.spec.js b/test/searching/maximum-subarray.spec.js
@@ -0,0 +1,29 @@
+var maxSubArray = require('../../src/searching/maximum-subarray').maxSubarray;
+
+describe('Maximum subarray', function() {
+  'use strict';
+
+  it('should work with empty arrays', function() {
+    expect(maxSubArray([])).toBeUndefined();
+  });
+
+  it('should return the only element when an array with single element is passed', function() {
+    expect(maxSubArray([42])).toBe(42);
+  });
+
+  it('should return the only negative element when an array with single element is passed', function() {
+    expect(maxSubArray([-42])).toBe(-42);
+  });
+
+  it('should return the zero when an array with single element, which is zero is passed', function() {
+    expect(maxSubArray([0])).toBe(0);
+  });
+
+  it('should return the max sum of a subarray', function() {
+    expect(maxSubArray([1, -1, 2, 3, -1])).toBe(5);
+  });
+
+  it('should return the max negative number when array with negative numbers is provided', function() {
+    expect(maxSubArray([-10, -1, -2, -3, -1])).toBe(-1);
+  });
+});

Original file line number	Diff line number	Diff line change
`@@ -55,7 +55,7 @@`
`55`	`55`
`56`	`56`	`/**`
`57`	`57`	`* Simple non-crypto hash used to hash keys, which determines`
`58`		`- * while bucket the value will be placed in.`
	`58`	`+ * which bucket the value will be placed in.`
`59`	`59`	`* A javascript implementation of Java's 32bitint hash.`
`60`	`60`	`*`
`61`	`61`	`* @public`