If we change "increasing" to "non-decreasing"...


  • 1

    Hello, everybody:

    I think the relax-based method, either DP or DFS (or both) , is working fine with the complexity O(mn).

    In terms of graph model, the original problem input is a DAG(directed acrylic graph). However "non-decreasing" path requires bi-directional edge between neighbors with the same value. That is, the graph is not a DAG anymore.

    If the problem changes to longest "non-decreasing" instead of "increasing" path, anyone thinks it is still doable in O(mn) time? How? Or Why not?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.