-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path53_Maximum_Subarray.java
More file actions
65 lines (58 loc) · 1.66 KB
/
53_Maximum_Subarray.java
File metadata and controls
65 lines (58 loc) · 1.66 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
* 53. Maximum Subarray
* Target: Find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
* Difficulty：Easy
* Classification：Array, Divide and Conquer, Dynamic Programming
*/
/*
* Solution 1
* 2019-06-23 Runtime: 1 ms
* Algorithm: => DP.
* Time complexity: O(n). Space complexity: O(n).
*/
class Solution {
public int maxSubArray(int[] nums) {
int num_pre = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
num_pre = Math.max(num_pre + nums[i], nums[i]);
max = Math.max(max, num_pre);
}
return max;
}
}
/*
* Solution 2
* 2019-06-24 Runtime: 1 ms
* Algorithm: => Divide and Conquer.
* Time complexity: O(n*logn).
*/
class Solution {
public int maxSubArray(int[] nums) {
return SubArr(nums, 0, nums.length - 1);
}
private int SubArr(int[] nums, int lo, int hi) {
if (lo == hi) {
return nums[lo];
}
int mid = (lo + hi) / 2;
return Math.max(Math.max(SubArr(nums, lo, mid), SubArr(nums, mid + 1, hi)), maxSubArrCross(nums, lo, mid, hi));
}
private int maxSubArrCross(int[] nums, int lo, int mid, int hi) {
int sum = 0, sum_l = Integer.MIN_VALUE, sum_r = Integer.MIN_VALUE;
for (int i = mid; i >= lo; i--) {
sum += nums[i];
if (sum > sum_l) {
sum_l = sum;
}
}
sum = 0;
for (int j = mid + 1; j <= hi; j++) {
sum += nums[j];
if (sum > sum_r) {
sum_r = sum;
}
}
return sum_l + sum_r;
}
}