How can i space optimize this ?

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

Автор Aniket54, история, 3 года назад, По-английски

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

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.

dp, more dp

Aniket54
3 года назад
6

Комментарии (4)

Показать архивные | Написать комментарий?

alpha1215

3 года назад, скрыть # |

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]

→ Ответить

Aniket54

3 года назад, скрыть # ^ |

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

→ Ответить

alpha1215

3 года назад, скрыть # ^ |

we can do it in O(n) space

code

    vector<int> dp(n);
    for(int i = 0; i < n; i++) {
        dp[i] = 1;
        for(int j = 0; j < i; j++) {
            if(A[j] <= A[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    cout << *max_element(dp.begin(), dp.end());

→ Ответить

iLLuSiOnZ

3 года назад, скрыть # |

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 ->

→ Ответить