FilesExpand file tree

 master

/

MaximumSubarray.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

33 lines (31 loc) · 1.04 KB

 master

/

MaximumSubarray.java

Top

File metadata and controls

• Code
• Blame

33 lines (31 loc) · 1.04 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

/*

Author: King, wangjingui@outlook.com

Date: Dec 25, 2014

Problem: Maximum Subarray

Difficulty: Medium

Source: https://oj.leetcode.com/problems/maximum-subarray/

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

Solution: dp.

*/

public class Solution {

public int maxSubArray_1(int[] A) {

if (A.length == 0) return 0;

int minVal = Math.min(A[0],0), res = A[0], sum = A[0];

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

sum += A[i];

res = Math.max(res, sum - minVal);

minVal = Math.min(minVal, sum);

}

return res;

}

public int maxSubArray_2(int[] A) {

if (A.length == 0) return 0;

int dp = A[0], res = A[0];

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

dp = Math.max(A[i], dp + A[i]);

res = Math.max(res, dp);

}

return res;

}

}