forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHC-kang.ts
More file actions
93 lines (77 loc) ยท 1.99 KB
/
HC-kang.ts
File metadata and controls
93 lines (77 loc) ยท 1.99 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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/**
* https://leetcode.com/problems/maximum-subarray
* Kadane's Algorithm
* T.C. O(n)
* S.C. O(1)
*/
function maxSubArray(nums: number[]): number {
let maxSum = nums[0];
for (let i = 1; i < nums.length; i++) {
nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
maxSum = Math.max(maxSum, nums[i]);
}
return maxSum;
}
/**
* Divide and Conquer version
* T.C. O(n log n)
* S.C. O(log n) - call stack
*/
function maxSubArray(nums: number[]): number {
function maxSubArrayHelper(
nums: number[],
left: number,
right: number
): number {
if (left === right) return nums[left];
const mid = (left + right) >> 1;
const leftMax = maxSubArrayHelper(nums, left, mid);
const rightMax = maxSubArrayHelper(nums, mid + 1, right);
let leftSum = -Infinity;
let rightSum = -Infinity;
let sum = 0;
for (let i = mid; i >= left; i--) {
sum += nums[i];
leftSum = Math.max(leftSum, sum);
}
sum = 0;
for (let i = mid + 1; i <= right; i++) {
sum += nums[i];
rightSum = Math.max(rightSum, sum);
}
return Math.max(leftMax, rightMax, leftSum + rightSum);
}
return maxSubArrayHelper(nums, 0, nums.length - 1);
}
/**
* Iterative version
* T.C. O(n log n)
* S.C. O(log n) - call stack
*/
function maxSubArray(nums: number[]): number {
const stack = [[0, nums.length - 1]];
let maxSum = nums[0];
while (stack.length) {
const [left, right] = stack.pop()!;
if (left === right) {
maxSum = Math.max(maxSum, nums[left]);
continue;
}
const mid = (left + right) >> 1;
stack.push([left, mid], [mid + 1, right]);
let leftSum = -Infinity;
let rightSum = -Infinity;
let sum = 0;
for (let i = mid; i >= left; i--) {
sum += nums[i];
leftSum = Math.max(leftSum, sum);
}
sum = 0;
for (let i = mid + 1; i <= right; i++) {
sum += nums[i];
rightSum = Math.max(rightSum, sum);
}
maxSum = Math.max(maxSum, leftSum + rightSum);
}
return maxSum;
}