Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit16a2b5c

Browse files
committed
04.01 (1) global and local dp
1 parent1eb47cd commit16a2b5c

File tree

3 files changed

+111
-3
lines changed

3 files changed

+111
-3
lines changed
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
/**
2+
* Time : O() ; Space: O()
3+
* @tag :
4+
* @by : Steven Cooks
5+
* @date: Sep 4, 2015
6+
***************************************************************************
7+
* Description:
8+
*
9+
* Given a sequence of integers, find the longest increasing subsequence (LIS).
10+
* You code should return the length of the LIS.
11+
*
12+
* Example
13+
* For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3
14+
* For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4
15+
*
16+
***************************************************************************
17+
* {@link http://www.lintcode.com/en/problem/longest-increasing-subsequence/# }
18+
*/
19+
package_01_LongestIncreasingSubsequence;
20+
21+
/** see test {@link _01_LongestIncreasingSubsequence.SolutionTest } */
22+
publicclassSolution {
23+
24+
publicintlongestIncreasingSubsequence(int[]nums) {
25+
intn =nums.length;
26+
// dp[i] = length of longest subsequence that ending by nums[i]
27+
int[]dp =newint[n];
28+
intres =0;
29+
for (inti =0;i <n;i++) {
30+
intnum =nums[i];
31+
intlen =1;
32+
for (intj =i -1;j >=0;j--) {
33+
if (nums[j] <=num) {
34+
len =Math.max(len,dp[j] +1);
35+
}
36+
}
37+
dp[i] =len;
38+
res =Math.max(res,dp[i]);
39+
}
40+
returnres;
41+
}
42+
43+
}
Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package_01_LongestIncreasingSubsequence;
2+
3+
importstaticorg.junit.Assert.*;
4+
5+
importorg.junit.After;
6+
importorg.junit.Before;
7+
importorg.junit.Rule;
8+
importorg.junit.Test;
9+
importorg.junit.rules.Timeout;
10+
11+
publicclassSolutionTest {
12+
13+
/** Test method for {@link _01_LongestIncreasingSubsequence.Solution } */
14+
Solutionsolution;
15+
16+
@Rule
17+
publicTimeoutglobalTimeout =newTimeout(200);
18+
19+
@Before
20+
publicvoidsetUp()throwsException {
21+
solution =newSolution();
22+
}
23+
24+
@After
25+
publicvoidtearDown()throwsException {
26+
solution =null;
27+
}
28+
29+
// [1, 2, 3]
30+
@Test
31+
publicvoidTest1() {
32+
int[]nums = {5,4,1,2,3 };
33+
intactual =solution.longestIncreasingSubsequence(nums);
34+
intexpected =3;
35+
assertEquals(expected,actual);
36+
}
37+
38+
// [4, 4, 5, 7] or [2, 4, 5, 7]
39+
@Test
40+
publicvoidTest2() {
41+
int[]nums = {4,2,4,5,3,7 };
42+
intactual =solution.longestIncreasingSubsequence(nums);
43+
intexpected =4;
44+
assertEquals(expected,actual);
45+
}
46+
47+
// [1, 2, 3, 11]
48+
@Test
49+
publicvoidTest3() {
50+
int[]nums = {10,1,11,2,12,3,11 };
51+
intactual =solution.longestIncreasingSubsequence(nums);
52+
intexpected =4;
53+
assertEquals(expected,actual);
54+
}
55+
56+
@Test
57+
publicvoidTest4() {
58+
int[]nums = {4,2,4,5,3,7,3,3,3,3 };
59+
intactual =solution.longestIncreasingSubsequence(nums);
60+
intexpected =6;
61+
assertEquals(expected,actual);
62+
}
63+
64+
}

‎README.md

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@ Selected problems that are included in LintCode but are not included in Leetcode
1010
- not too brief explanation for problem
1111

1212
| problem| solution| tags| note|
13-
| :---| ----| ---------| -----|
14-
| 03.01|[Insert Node in Binary Search Tree](https://github.com/interviewcoder/lintcode/blob/master/03_binarytree%26divideconquer/_01_InsertNodeInABinarySearchTree/Solution.java)| BST;`LintCode Copyright`||
15-
| 03.02|[Search Range In Binary Search Tree](https://github.com/interviewcoder/lintcode/blob/master/03_binarytree%26divideconquer/_02_SearchRangeInBinarySearchTree/Solution.java)| Binary Search Tree| in-order + pruning|
13+
| ---| ----| ---------| -----|
14+
| 03.01|[Insert Node in Binary Search Tree](https://github.com/interviewcoder/lintcode/blob/master/03_binarytree%26divideconquer/_01_InsertNodeInABinarySearchTree/Solution.java)| BST`LintCode Copyright`||
15+
| 03.02|[Search Range In Binary Search Tree](https://github.com/interviewcoder/lintcode/blob/master/03_binarytree%26divideconquer/_02_SearchRangeInBinarySearchTree/Solution.java)| Binary Search Tree| in-order + pruning|
16+
| 04.01|[Longest Increasing Subsequence](https://github.com/interviewcoder/lintcode/blob/master/04dynamicprogrammingI/_01_LongestIncreasingSubsequence/Solution.java)| Dynamic Programming||

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp