1. 第一个数 X 第二个数 X 第三个数
2. 倒数第一个数 X 倒数第二个数 X 倒数第三个数
3. 第一个数 X 倒数第一个数 X 倒数第二个数
4. 第一个数 X 第二个数 X 倒数第一个数
class Solution(object):
def maximumProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
return max(nums[0]*nums[1]*nums[2],
nums[-1]*nums[-2]*nums[-3],
nums[0]*nums[-1]*nums[-2],
nums[0]*nums[1]*nums[-1])


$$d_1 \le d_2 \le \cdots \le d_m.$$

$$\sum_{i=1}^k t_i \le d_k.$$

from heapq import heappush, heappop

class Solution(object):
def scheduleCourse(self, courses):
"""
:type courses: List[List[int]]
:rtype: int
"""
courses.sort(key=lambda c: c[1])
h = []
s = courses[0][0]
heappush(h, -s)
for t, d in courses[1:]:
if s+t<=d:
heappush(h, -t)
s += t
elif h[0]+t<0:
s += h[0]+t
heappop(h)
heappush(h, -t)
return len(h)


$$f(i, j) = f(i-1, j) + f(i-1, j-1) + \cdots + f(i-1, 0);$$

$$f(i, j) = f(i-1, j) + f(i-1, j-1) + \cdots + f(i-1, j-i+1).$$

$$f(i, j) = f(i, j-1) + f(i-1, j);$$

$$f(i, j) = f(i, j-1) + f(i-1, j) - f(i-1, j-i).$$

class Solution(object):
def kInversePairs(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
M = 10**9+7
f = [[0]*(k+1) for _ in xrange(n+1)]
for i in xrange(1, n+1):
f[i][0] = 1
c = min(k, i*(i-1)/2)
for j in xrange(1, min(i, c+1)):
f[i][j] = (f[i][j-1]+f[i-1][j]) % M
for j in xrange(i, c+1):
f[i][j] = (f[i][j-1]+f[i-1][j]-f[i-1][j-i]) % M
return f[n][k]


class Excel(object):

def __init__(self, H,W):
"""
:type H: int
:type W: str
"""
self.cell = {}
self.sums = {}
for i in xrange(1, H+1):
for j in xrange(ord(W)-ord('A')):
self.cell[i, j] = 0
self.sums[i, j] = []

def set(self, r, c, v):
"""
:type r: int
:type c: str
:type v: int
:rtype: void
"""
self.cell[r, ord(c)-ord('A')] = v
self.sums[r, ord(c)-ord('A')] = []

seen = set()
def dfs(r, c):
if not self.sums[r, c] or (r, c) in seen:
return self.cell[r, c]
ans = 0
for s in self.sums[r, c]:
if ':' not in s:
ans += dfs(int(s[1:]), ord(s[0])-ord('A'))
else:
s = s.split(':')
rb, cb = int(s[0][1:]), ord(s[0][0])-ord('A')
re, ce = int(s[1][1:]), ord(s[1][0])-ord('A')
for i in xrange(rb, re+1):
for j in xrange(cb, ce+1):
ans += dfs(i, j)
self.cell[r, c] = ans
return ans

for r, c in self.cell.keys():
dfs(r, c)

def get(self, r, c):
"""
:type r: int
:type c: str
:rtype: int
"""
return self.cell[r, ord(c)-ord('A')]

def sum(self, r, c, strs):
"""
:type r: int
:type c: str
:type strs: List[str]
:rtype: int
"""
c = ord(c) - ord('A')
self.sums[r, c] = strs
ans = 0
for s in strs:
if ':' not in s:
ans += self.cell[int(s[1:]), ord(s[0])-ord('A')]
else:
s = s.split(':')
rb, cb = int(s[0][1:]), ord(s[0][0])-ord('A')
re, ce = int(s[1][1:]), ord(s[1][0])-ord('A')
for i in xrange(rb, re+1):
for j in xrange(cb, ce+1):
ans += self.cell[i, j]
self.cell[r, c] = ans
return ans

# Your Excel object will be instantiated and called as such:
# obj = Excel(H, W)
# obj.set(r,c,v)
# param_2 = obj.get(r,c)
# param_3 = obj.sum(r,c,strs)