FilesExpand file tree

 master

/

Solution.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

64 lines (40 loc) · 1.41 KB

 master

/

Solution.java

Top

File metadata and controls

• Code
• Blame

64 lines (40 loc) · 1.41 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

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

/* Maximum subarray

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

* For example, give the array [-2,1,-3,4,-1,2,1,-5,4].

* the continuous subarray [4,-1,2,1] has the largest sum = 6.

*/

public class Solution {

public int maxSubArray(int[] nums) {

if (nums == null || nums.length == 0) {

return 0;

}

//use dp

int global_max = nums[0];

//m[i] represents the maximum subarray sum from any position before i to ith position,(ending at ith position!!)

//base case:

m[0] = nums[0];

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

if (m[i-1] <= 0) {

m[i] = nums[i];

}else {

m[i] = m[i-1] + nums[i];

}

if (global_max < m[i]) {

global_max = m[i];

}

}

return global_max;

}//end maxSubArray

public int largestSum(int[] array) {

if (array == null || array.length == 0) {

return 0;

}

int global_max = array[0];

int cur_max = array[0];

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

cur_max = Math.max(cur_max + array[i], array[i]);

global_max = Math.max(global_max, cur_max);

}//end for loop

return global_max;

}//end largestSum

}//end class Solution