forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsunjae95.js
More file actions
81 lines (63 loc) Β· 1.75 KB
/
sunjae95.js
File metadata and controls
81 lines (63 loc) Β· 1.75 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
/**
* @description
* brainstorming:
* 1. memoization, recursive
* 2. palindromic-substring custom
*/
/**
* brainstorming solve 1
* result: fail because time limited
*
* time complexity: O(n^2)
* space complexity: O(n^2)
*/
var maxProduct = function (nums) {
let answer = nums[0];
const memo = Array.from({ length: nums.length }, () =>
Array.from({ length: nums.length }, () => null)
);
const recursive = (left, right) => {
if (memo[left][right] !== null) return memo[left][right];
if (left === right) {
memo[left][right] = nums[left];
answer = Math.max(answer, nums[left]);
return nums[left];
}
const removedLeft = recursive(left + 1, right);
recursive(left, right - 1);
memo[left][right] = nums[left] * removedLeft;
answer = Math.max(answer, memo[left][right]);
return removedLeft;
};
recursive(0, nums.length - 1);
return answer;
};
/**
* brainstorming solve 2
* result: fail because time limited
*
* time complexity: O(n^2)
* space complexity: O(n)
*/
var maxProduct = function (nums) {
let answer = nums[0];
for (let i = 0; i < nums.length; i++) {
let [start, end] = [i, i];
let product = nums[i];
answer = Math.max(answer, product);
while (start >= 0 && end < nums.length) {
if (start !== end) product = product * nums[start] * nums[end];
answer = Math.max(answer, product);
[start, end] = [start - 1, end + 1];
}
product = nums[i];
[start, end] = [i, i + 1];
while (start >= 0 && end < nums.length) {
if (start + 1 === end) product = product * nums[end];
else product = product * nums[start] * nums[end];
answer = Math.max(answer, product);
[start, end] = [start - 1, end + 1];
}
}
return answer;
};