forked from prateekshyap/DSA
-
Notifications
You must be signed in to change notification settings - Fork 0
/
LongestIncreasingSubsequence.java
111 lines (107 loc) · 3 KB
/
LongestIncreasingSubsequence.java
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
99
100
101
102
103
104
105
106
107
108
109
110
111
/*https://practice.geeksforgeeks.org/problems/longest-increasing-subsequence-1587115620/1*/
/*https://binarysearch.com/problems/Longest-Increasing-Subsequence*/
class Solution
{
static int longestSubsequence(int size, int a[])
{
int[] result = new int[size];
for (int i = 0; i < size; ++i)
result[i] = 1;
for (int i = 1; i < size; ++i)
{
for (int j = 0; j < i; ++j)
{
if (a[i] > a[j] && result[i] < result[j]+1)
result[i] = result[j]+1;
}
}
int max = result[0];
for (int i = 1; i < size; ++i)
max = Math.max(max, result[i]);
return max;
}
}
class Solution
{
//Function to find length of longest increasing subsequence.
static int longestSubsequence(int size, int a[])
{
// code here
ArrayList<Integer> list = new ArrayList<Integer>();
int result = 0, i = 0, low, high, mid, pos = -1;
list.add(a[i]);
for (i = 1; i < size; ++i)
{
if (a[i] > list.get(list.size()-1)) list.add(a[i]);
else
{
pos = -1;
low = 0;
high = list.size()-1;
while (low <= high)
{
mid = low+(high-low)/2;
if (list.get(mid) >= a[i])
{
pos = mid;
high = mid-1;
}
else low = mid+1;
}
list.set(pos,a[i]);
}
}
return list.size();
}
}
class Pair implements Comparable<Pair>
{
int a, b;
Pair(int a, int b)
{
this.a = a;
this.b = b;
}
@Override
public int compareTo(Pair other)
{
return 0;
}
@Override
public String toString()
{
return "("+a+","+b+")";
}
}
class Solution {
Integer[] table;
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes,(a,b)->(a[0] == b[0] ? b[1]-a[1] : a[0]-b[0]));
ArrayList<Pair> list = new ArrayList<Pair>();
int result = 0, i = 0, low, high, mid, pos = -1;
list.add(new Pair(envelopes[i][0],envelopes[i][1]));
for (i = 1; i < envelopes.length; ++i)
{
if (envelopes[i][1] > list.get(list.size()-1).b) list.add(new Pair(envelopes[i][0],envelopes[i][1]));
else
{
pos = -1;
low = 0;
high = list.size()-1;
while (low <= high)
{
mid = low+(high-low)/2;
if (list.get(mid).b < envelopes[i][1])
low = mid+1;
else
{
pos = mid;
high = mid-1;
}
}
list.set(pos,new Pair(envelopes[i][0],envelopes[i][1]));
}
}
return list.size();
}
}