forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathkimyoung.js
More file actions
28 lines (23 loc) ยท 876 Bytes
/
kimyoung.js
File metadata and controls
28 lines (23 loc) ยท 876 Bytes
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
var maxProduct = function (nums) { // brute force approach - doesn't pass leetcode (Time Limit Exceeded)
let maxProduct = -Infinity;
for (let i = 0; i < nums.length; i++) { // get subarrays
for (let j = i; j < nums.length; j++) {
let prod = nums.slice(i, j + 1).reduce((acc, el) => acc *= el, 1);
maxProduct = Math.max(prod, maxProduct);
}
}
return maxProduct;
};
// time - O(n^3) double for loop * reduce()
// space - O(1)
var maxProduct = function (nums) { // DP approach
let result = nums[0];
let [min, max] = [1, 1];
for (const num of nums) {
[min, max] = [Math.min(num * min, num * max, num), Math.max(num * min, num * max, num)];
result = Math.max(max, result);
}
return result;
};
// time - O(n) looping through nums once
// space - O(1) extra memory irrelevant to input