class Solution(object):
def findLengthOfLCIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ans = i = 0
while i < len(nums):
j = i + 1
while j < len(nums) and nums[j] > nums[j-1]:
j += 1
ans = max(ans, j-i)
i = j
return ans


class MagicDictionary(object):

def __init__(self):
"""
Initialize your data structure here.
"""
self.words = set()

def buildDict(self, dict):
"""
Build a dictionary through a list of words
:type dict: List[str]
:rtype: void
"""
self.words = set(dict)

def search(self, word):
"""
Returns if there is any word in the trie that equals to the given word after modifying exactly one character
:type word: str
:rtype: bool
"""
for i in xrange(len(word)):
for j in xrange(26):
c = chr(ord('a')+j)
if c == word[i]:
continue
tmp = word[:i] + c + word[i+1:]
if tmp in self.words:
return True
return False

# Your MagicDictionary object will be instantiated and called as such:
# obj = MagicDictionary()
# obj.buildDict(dict)
# param_2 = obj.search(word)


O(n2m2)算法：因为每个点最多跟四个点相邻，所以用BFS写最短路径的算法复杂度是O(nm)。从(0, 0)出发，从小到大遍历所有点需要求O(nm)条最短路径。为了快速从小到大遍历所有点，我们需要将所有大于1的点从小到大先排好序。

class Node {
public:
int x, y, v;
Node(int a=0, int b=0, int c=0): x(a), y(b), v(c) {}
};

class Solution {
public:
int cutOffTree(vector<vector<int>>& forest) {
int n = forest.size(), m = forest[0].size();
int ans = 0;
vector<Node> order;

for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
if (forest[i][j] > 1)
order.push_back(Node(i, j, forest[i][j]));

sort(order.begin(), order.end(), [](const Node& lhs, const Node &rhs)->bool {
return lhs.v < rhs.v;
});

int x = 0, y = 0;
for (auto p: order) {
int v = shortestPath(x, y, p.x, p.y, forest);
if (v == -1)
return -1;
ans += v;
x = p.x;
y = p.y;
}
return ans;
}

int shortestPath(int i, int j, int k, int l, vector<vector<int>>& forest) {
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n = forest.size(), m = forest[0].size();
vector<Node> stack;
unordered_set<int> visited;

stack.push_back(Node(i, j, 0));
visited.insert(i*m + j);
for (int cur = 0; cur < stack.size(); cur ++) {
Node p = stack[cur];
if (p.x == k && p.y == l)
return p.v;
for (int d = 0; d < 4; d ++) {
int nx = p.x+dx[d];
int ny = p.y+dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= m)
continue;
if (forest[nx][ny] == 0 || visited.find(nx*m + ny) != visited.end())
continue;
visited.insert(nx*m +ny);
stack.push_back(Node(nx, ny, p.v+1));
}
}
return -1;
}
};


class Solution(object):
def findNumberOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
dp = [1] * len(nums)
f = [1] * len(nums)
ans = ml = 1
for i in xrange(1, len(nums)):
for j in xrange(i):
if nums[j] < nums[i]:
if dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
f[i] = f[j]
elif dp[j] + 1 == dp[i]:
f[i] += f[j]
if dp[i] > ml:
ml = dp[i]
ans = f[i]
elif dp[i] == ml:
ans += f[i]
return ans