FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
coding-Interview/LongestIncreasingSubsequence.java at master · arjunmullick/coding-Interview · GitHub
arjunmullick
/
coding-Interview
Public
Notifications
You must be signed in to change notification settings
Fork
1
Star
3
Code
Issues
0
Pull requests
0
Actions
Projects
Wiki
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
coding-Interview
/
LongestIncreasingSubsequence.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
98 lines (88 loc) · 2.59 KB
Breadcrumbs
coding-Interview
/
LongestIncreasingSubsequence.java
Copy path
File metadata and controls
98 lines (88 loc) · 2.59 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
package
com
.
leetcode
;
import
java
.
util
.
Arrays
;
public
class
LongestIncreasingSubsequence
{
//https://leetcode.com/problems/longest-increasing-subsequence/
class
Solution
{
//[10,9,2,5,3,7,101,18]
//[1,1,1,2,2,3,4,1]
//at value 3 we need visibility of value 2 and its longest sub seq count
//We can always go back to index j where num[j] < num[i] - j<i . This search will N^2 why not calculate starting at each j
// then search max in count array memo
//N^2 better than 2^N brute force
public
int
lengthOfLIS
(
int
[]
nums
) {
if
(
nums
.
length
<=
1
)
return
nums
.
length
;
int
memo
[] =
new
int
[
nums
.
length
];
//to store value of LIS at index position
for
(
int
i
=
0
;
i
<
memo
.
length
;
i
++){
memo
[
i
] =
1
;
}
for
(
int
i
=
0
;
i
<
nums
.
length
;
i
++){
for
(
int
j
=
i
+
1
;
j
<
nums
.
length
;
j
++){
if
(
nums
[
j
] >
nums
[
i
]){
memo
[
j
] =
Math
.
max
(
memo
[
j
] ,
memo
[
i
]+
1
);
}
}
}
int
result
=
0
;
for
(
int
i
=
0
;
i
<
memo
.
length
;
i
++){
//System.out.print(memo[i] + " ");
result
=
Math
.
max
(
result
,
memo
[
i
]);
}
return
result
;
}
}
}
/**
* Good for discussion
*
*ALTERNATE APPROACH O(N LogN)
*
* insert first number in empty array at 0 pos .
* Run binary search every time a new number is added . Find number just lesser than it
* if found insert
* else replace index 0 and start again
* [10,9,2,5,3,7,101,18]
* 10 0 0 0 0 0 0 0
* 9 0 0 0 0 0 0 0
* 2 0 0 0 0 0 0 0
* 2 5 0 0 0 0 0 0
* 2 3 0 0 0 0 0 0
* 2 3 7 0 0 0 0 0
* 2 3 7 101 0 0 0 0
* 2 3 7 18 0 0 0 0
*/
/*
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int len = 0;
for (int num : nums) {
int i = Arrays.binarySearch(dp, 0, len, num);
//System.out.println(num + " " + i+ " " + len + " /");
if (i < 0) {
i = -(i + 1);
}
dp[i] = num;
if (i == len) {
len++;
}
}
return len;
}
//OR
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int i = 0, j = size;
while (i != j) {
int m = (i + j) / 2;
if (tails[m] < x)
i = m + 1;
else
j = m;
}
tails[i] = x;
if (i == size) ++size;
}
return size;
}
*/
Back
|
FazBrowse Home
|
New Git URL