package leetcode;
/**
* 673. Number of Longest Increasing Subsequence
* <p>
* Given an unsorted array of integers, find the number of longest increasing subsequence.
* <p>
* Example 1:
* Input: [1,3,5,4,7]
* Output: 2
* Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].
* Example 2:
* Input: [2,2,2,2,2]
* Output: 5
* Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.
* Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.
*/
public class NumberOfLIS673 {
// solution: dynamic programming(DP), at nums[i], we can get longest length[i], and counts[i],
// for each i < j, with nums[i] < nums[j], we compare the longest length length[i] and length[j],
// if longest length[j] + 1 == length[i] -> append nums[j] into longest length[i] -> length[i] + 1.
// thus the total count will be count[i] + count[j]
// if longest length[j] + 1 > length[i] -> we need to update longest length[i] = length[j] + 1,
// and update count -> count[i] = count[j].
public int findNumberOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
int maxLen = 0;
int res = 0;
int[] len = new int[n];
int[] cnt = new int[n];
for (int i = 0; i < n; i++) {
len[i] = cnt[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
if (len[i] == len[j] + 1) cnt[i] += cnt[j];
if (len[i] < len[j] + 1) {
len[i] = len[j] + 1;
cnt[i] = cnt[j];
}
}
}
if (maxLen == len[i]) res += cnt[i];
if (maxLen < len[i]) {
maxLen = len[i];
res = cnt[i];
}
}
return res;
}
}[R] - Why Python is slow
Was discussing this topic with a friend who uses Python for development. And found some good resources online.
This article explains why Python is slow from 3 different views:
- It is GIL(Global Interpreter Lock)
- Python is interpreted not compiled language
- Python is Dynamically typed language
About why Python is slow, there are some answers on Quora - why is Python slower than other languages
And Article and discussion on HackNews - why Python is slow?
[T] - BetterTouchTool
Mac OS has its own powerful trackpads, forth touch, e.g. you can drag a window to the side of the screen to rearrange the window to split into left/right half, or full screen etc.
With BetterTouchTool, you can do more, check it out and play with it.
A beginner friend guid for starting to play around with Kubernetes.
It includes a brief introduction of what is k8s, basic concepts of nodes, pods, cluster.
Steps on how to deploy an application to k8s cluster.