FilesExpand file tree

 master

/

MaximumSumSubArray.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

28 lines (22 loc) · 1.1 KB

 master

/

MaximumSumSubArray.java

Copy path

Top

File metadata and controls

• Code
• Blame

28 lines (22 loc) · 1.1 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

/*

this problem was discussed by Jon Bentley (Sep. 1984 Vol. 27 No. 9 Communications of the ACM P885)

the paragraph below was copied from his paper (with a little modifications)

algorithm that operates on arrays: it starts at the left end (element A[1]) and scans through to the right end (element A[n]), keeping track of the maximum sum subvector seen so far. The maximum is initially A[0]. Suppose we've solved the problem for A[1 .. i - 1]; how can we extend that to A[1 .. i]? The maximum

sum in the first I elements is either the maximum sum in the first i - 1 elements (which we'll call MaxSoFar), or it is that of a subvector that ends in position i (which we'll call MaxEndingHere).

MaxEndingHere is either A[i] plus the previous MaxEndingHere, or just A[i], whichever is larger.

O(n)

O(1)

*/

public class Solution

{

public int maxSubArray(int[] nums)

{

int max = nums[0], maxSoFar = nums[0];

for(int i=1; i < nums.length; i++)

{

maxSoFar = maxSoFar > 0 ? maxSoFar + nums[i] : nums[i];

max = Math.max(maxSoFar, max);

}

return max;

}

}