-
Notifications
You must be signed in to change notification settings - Fork 10
Expand file tree
/
Copy pathSolution53.java
More file actions
44 lines (42 loc) · 1.16 KB
/
Copy pathSolution53.java
File metadata and controls
44 lines (42 loc) · 1.16 KB
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);
}
}