Aniket54's blog

How can i space optimize this ?
By Aniket54, history, 8 months ago, In English

I'm getting MLE at test 33 here is the problem

and my submission

here i used LIS dp -> time O(N^2), space O(N^2) .... i don't know how to convert space to O(n) and also at the same time get a particular solution.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Aniket54 (previous revision, new revision, compare).

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
for calculating  LIS 
let dp[j] denote longest increasing subseq including A[j] 
now to calculate dp[i] you just need to know dp[j] for all j < i;
dp[i] = max(dp[i], 1 + dp[j]) 
for all j < i and A[j] <= A[i]
→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i will not get a solution if i do this ...to get a solution we need whole dp table right we can't space optimize it to 1D array

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      we can do it in O(n) space

      code
      → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Finding the length of LIS can be done by DP where $$$dp[i]$$$ is the maximum LIS having $$$a[i]$$$ as its last element.
To print the LIS, you can maintain a parent array which stores for each index, the index of the previous element of its LIS.
This can be done in $$$O(N^2)$$$ time and $$$O(N)$$$ space.
Submission Link ->254290850

LOGIC ->
→ Reply