class Solution {
public:
int maxProduct(int length) {
// write your solution here
vector<int> memo;
// memo[i] is the max for length = i
memo.push_back(1);
for (int i = 2; i <= length; i++){
int curr_max = 1;
for (int j = 1; j <= i-1; j++){
int candidate = memo[j] * (i-j);
curr_max = curr_max > candidate? curr_max : candidate;
}
memo.push_back(curr_max);
}
}
return memo[length-1];
};
Loop version... Time complexity is O(n^2)
Mistake:
- Values in memo represent for that length of rope, we HAVE to make at least one cut;
- What about no-cut? Need to take max again. See solution updated.
Mistake:
- Values in memo represent for that length of rope, we HAVE to make at least one cut;
- What about no-cut? Need to take max again. See solution updated.
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.