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?