FilesExpand file tree

 master

/

MaximumSubarray.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

37 lines (37 loc) · 1.13 KB

 master

/

MaximumSubarray.java

Copy path

Top

File metadata and controls

• Code
• Blame

37 lines (37 loc) · 1.13 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

/**

* Created by YGZ on 2016/3/8.

*/

public class MaximumSubarray {

/*public int maxSubArray(int[] nums) {

if (nums.length<1) return 0;

int length = nums.length;

int res = nums[0];

for (int i=0;i<length;i++){

if (nums[i]>0){

int sum = 0;

for (int j=i;j<length;j++){

sum += nums[j];

if (sum>res) res = sum;

}

}else{

if (res<nums[i]){

res = nums[i];

}

}

}

return res;

}*/

public static int maxSubArray(int[] A) {

int maxSoFar=A[0], maxEndingHere=A[0];

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

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

maxSoFar=Math.max(maxSoFar, maxEndingHere);

}

return maxSoFar;

}

public static void main(String agrs[]){

int[] nums = {-2,1,-3,4,-1,2,1,-5,4};

MaximumSubarray maximumSubarray = new MaximumSubarray();

System.out.println(maximumSubarray.maxSubArray(nums));

}

}