FilesExpand file tree

 master

/

maximum-subarray.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

35 lines (31 loc) · 1.01 KB

 master

/

maximum-subarray.js

Copy path

Top

File metadata and controls

• Code
• Blame

35 lines (31 loc) · 1.01 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

(function (exports) {

'use strict';

/**

* Finds the maximum sum of the elements of a subarray in a given array

* using the Kadane's algorithm.

* For example, for the sequence of values -2, 1, -3, 4, -1, 2, 1, -5, 4

* the contiguous subarray with the largest sum is 4, -1, 2, 1, with sum 6.

* <br><br>

* Time complexity: O(N).

*

* @example

* var max = require('path-to-algorithms/src/searching/'+

* 'maximum-subarray').maxSubarray;

* console.log(max([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6

*

* @public

* @module searching/maximum-subarray

* @param {Array} array Input array.

* @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]);

max = Math.max(max, currentMax);

}

return max;

}

exports.maxSubarray = maxSubarray;

})(typeof window === 'undefined' ? module.exports : window);