forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathgreatest-sum-divisible-by-three.py
More file actions
66 lines (53 loc) · 1.94 KB
/
greatest-sum-divisible-by-three.py
File metadata and controls
66 lines (53 loc) · 1.94 KB
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#DP
"""
Time: O(N)
Space: O(N). Can reduce to O(1).
dp[i][0] max number n, which n%3==0, considering nums[0~i-1]
dp[i][1] max number n, which n%3==1, considering nums[0~i-1]
dp[i][2] max number n, which n%3==2, considering nums[0~i-1]
"""
class Solution(object):
def maxSumDivThree(self, nums):
dp = [[0]*3 for _ in xrange(len(nums)+1)]
for i in xrange(len(nums)+1):
if i==0:
dp[i][0] = 0
dp[i][1] = float('-inf')
dp[i][2] = float('-inf')
continue
n = nums[i-1]
if n%3==0:
dp[i][0] = max(dp[i-1][0], dp[i-1][0]+n)
dp[i][1] = max(dp[i-1][1], dp[i-1][1]+n)
dp[i][2] = max(dp[i-1][2], dp[i-1][2]+n)
elif n%3==1:
dp[i][0] = max(dp[i-1][0], dp[i-1][2]+n)
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+n)
dp[i][2] = max(dp[i-1][2], dp[i-1][1]+n)
elif n%3==2:
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+n)
dp[i][1] = max(dp[i-1][1], dp[i-1][2]+n)
dp[i][2] = max(dp[i-1][2], dp[i-1][0]+n)
return dp[-1][0]
# Greedy
class Solution(object):
def videoStitching(self, clips, T):
if T==0: return 0
if not clips: return -1
clips.sort()
print clips
if clips[0][0]!=0: return -1
if clips[0][1]>=T: return 1
count = 0
i = 0
rightMost = 0
while i<len(clips):
right = rightMost
while i<len(clips) and clips[i][0]<=rightMost:
right = max(right, clips[i][1])
i += 1
if rightMost==right: return -1 #rightMost cannot be update anymore
rightMost = right
count += 1
if rightMost >= T: return count
return -1