FilesExpand file tree

 master

/

KadaneAlgo.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

25 lines (24 loc) · 943 Bytes

 master

/

KadaneAlgo.js

Copy path

Top

File metadata and controls

• Code
• Blame

25 lines (24 loc) · 943 Bytes

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

/* Kadane's algorithm is one of the most efficient ways to

* calculate the maximum contiguous subarray sum for a given array.

* Below is the implementation of Kadane's algorithm along with

* some sample test cases.

* There might be a special case in this problem if al the elements

* of the given array are negative. In such a case, the maximum negative

* value present in the array is the answer.

*

* Reference article :- https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

*/

export function kadaneAlgo (array) {

let cumulativeSum = 0

let maxSum = Number.NEGATIVE_INFINITY // maxSum has the least possible value

for (let i = 0; i < array.length; i++) {

cumulativeSum = cumulativeSum + array[i]

if (maxSum < cumulativeSum) {

maxSum = cumulativeSum

} else if (cumulativeSum < 0) {

cumulativeSum = 0

}

}

return maxSum

// This function returns largest sum contiguous sum in a array

}