Блог пользователя Aniket54

How can i space optimize this ?
Автор Aniket54, история, 8 месяцев назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится 
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]
→ Ответить
  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      we can do it in O(n) space

      code
      → Ответить
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ->
→ Ответить