Linked Questions
39 questions linked to/from How to determine the longest increasing subsequence using dynamic programming?
3
votes
2
answers
5k
views
How many minimum numbers of characters from a given string S, should delete to make it a sorted string [duplicate]
I need to find the minimum number of deletions required to make string sorted.
Sample Test case:
# Given Input:
teststr = "abcb"
# Expected output:
1
# Explanation
# In this test case, if I delete ...
- 2,678
1
vote
2
answers
3k
views
Find The Longest Increasing Sequence in a 2 Dimensional Array [duplicate]
I've been working on this problem for awhile and couldn't come up with the solution; I hope you can help out..
I'm trying to find the longest increasing sequence of numbers. For example, if I have ...
-3
votes
1
answer
746
views
Algorithm for Longest Increasing Subsequence timing out [duplicate]
I am solving the Longest Subsequence problem at HackerRank. I am using Dynamic Programming algorithm to solve the Longest subsequence problem. The time complexity for my algorithm is O(n^2). Although ...
- 167
0
votes
1
answer
122
views
Given an array, find maximal sorted subset [duplicate]
I want to find the maximal subset of an array which is sorted in ascending order
Say I have
a = [2, 1, 4, 6, 7]
a_max_subset = [1, 4, 6, 7]
b = [4, 1, 2]
b_max_subset = [1, 2]
c = [2, 5, 13, 8, 6,...
- 1,019
2
votes
1
answer
61
views
Efficient Algorithm for Finding the Longest Increasing Subsequence [duplicate]
I'm working on a project where I need to find the longest increasing subsequence (LIS) from a given array of integers. However, the array can be quite large, so I'm looking for an efficient algorithm ...
0
votes
0
answers
28
views
How do i check what values do I have to remove from a list of numbers to make it monotonic? (newest python) [duplicate]
Basically lets say I have a list of 6 integers: 1 1 2 1 1 1
My existing algorithm knows that the list isn't monotonic, and knows that the highest monotonic sub division is 1 1 1.
What it needs to know ...
17
votes
11
answers
29k
views
Dynamic programming: Find longest subsequence that is zig zag
Can anyone please help me understand the core logic behind the solution to a problem mentioned at http://www.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493
A zig zag sequence is one ...
- 13k
7
votes
7
answers
6k
views
Longest Increasing Subsequence (LIS) with two numbers
How to find the length of LIS using two numbers.
For example,
[(1,2) (7,8) (3,4) (5,6)]
In the above array sequence, the length of LIS would be 3. i.e,
[(1,2) (3,4) (5,6)]
Any idea?
- 2,449
10
votes
3
answers
19k
views
How can I find the maximum sum of a sub-sequence using dynamic programming?
I'm re-reading Skiena's Algorithm Design Manual to catch up on some stuff I've forgotten since school, and I'm a little baffled by his descriptions of Dynamic Programming. I've looked it up on ...
- 26.5k
7
votes
4
answers
2k
views
Finding minimal distance between unsorted and sorted lists
Let A be a list and S a sorted list of the same elements. Assume all elements are different. How do I find a minimal set of "moves" (move X before Y (or end)) that turns A into S?
Examples:
A = [8,1,...
- 216k
4
votes
4
answers
5k
views
sort an array with minimum moves
I've come across this question:
there is n+1 loading docks. a permutation of boxes 1->n is placed on
the first n. there is a fork that can move one box to an empty
location at a time. Give an ...
- 23.7k
5
votes
4
answers
5k
views
How to find increasing subsequence of numbers with maximum sum?
How to find increasing subsequence of numbers with maximum sum.
I find O(N^2) but I want to know O(N log N).
Thanks!
- 1,045
4
votes
2
answers
4k
views
How does algorithm for Longest increasing subsequence [O(nlogn)] work?
I found algorithm mentioned in The Hitchhiker’s Guide to the Programming Contests (note: this implementation assumes there are no duplicates in the list):
set<int> st;
set<int>::iterator ...
- 4,103
2
votes
1
answer
3k
views
Longest Incresing Subsequence to solve building bridge
I've something that bothers me. I'm trying to solve building bridge problem which have this information as a instruction.
Building Bridges
Consider a 2-D map with a horizontal river passing ...
- 23
0
votes
4
answers
1k
views
Example of 1+2+3+...+n sum algorithm
What is the complexity of T(n)=1+2+3+...+n? I know that the answer is O(n^2). What is an example of an algorithm that has runtime T(n)?
EDIT: I was not talking about computing the sum 1+2+3+...+n, ...
- 143