FilesExpand file tree

 master

/

Solution53.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

44 lines (42 loc) · 1.16 KB

 master

/

Solution53.java

Copy path

Top

File metadata and controls

• Code
• Blame

44 lines (42 loc) · 1.16 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

package leetcode.all.solution1_100;

/**

* 53.最大子序和.

* 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

*

* 示例:

* 输入: [-2,1,-3,4,-1,2,1,-5,4],

* 输出: 6

* 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

*

* 进阶:

*

* 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

*

* @author 刘壮飞

* https://github.com/zfman.

* https://blog.csdn.net/lzhuangfei.

*/

public class Solution53 {

public int maxSubArray(int[] nums) {

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

int sum = nums[0];

int tmp=nums[0];

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

if(tmp>0){

tmp+=nums[i];

if(tmp>sum) sum=tmp;

}else{

tmp=nums[i];

if(tmp>sum) sum=tmp;

}

}

return sum;

}

public static void main(String[] args) {

int[] nums = {

-2, 1, -3, 4, -1, 2, 1, -5, 4

};

int r = new Solution53().maxSubArray(nums);

System.out.println(r);

}

}