-
Notifications
You must be signed in to change notification settings - Fork 0
/
Solution.java
46 lines (43 loc) · 1.66 KB
/
Solution.java
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
package week7.E53MaximumSubarray;
/**
* ******************************************************************
* 日 期: 2020-01-21 星期二
* ******************************************************************
* 题 目: [53]Maximum Sub个整数array
* * //给定一数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
* //
* // 示例:
* //
* // 输入: [-2,1,-3,4,-1,2,1,-5,4],
* //输出: 6
* //解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
* //
* //
* // 进阶:
* //
* // 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。
* // Related Topics 数组 分治算法 动态规划
* ******************************************************************
* 执行耗时: 1ms,击败了 99.96% 的Java用户
* 内存消耗: 37.9MB,击败了 79.62% 的Java用户
* ******************************************************************
* 个人总结:官方题解-动态规划解法
* ******************************************************************
*/
public class Solution {
public static void main (String[] args) {
Solution solution = new Solution();
solution.maxSubArray(new int[]{- 2, 1, - 3, 4, - 1, 2, 1, - 5, 4});
}
public int maxSubArray (int[] nums) {
int n = nums.length, maxSum = nums[0];
for (int i = 1; i < n; i++) {
// 直接替换数组里的值,数据里的值存放每个位置的最大和。
if (nums[i - 1] > 0) {
nums[i] += nums[i - 1];
}
maxSum = Math.max(nums[i], maxSum);
}
return maxSum;
}
}