harkuli / supowit Goto Github PK

Problem

While the matched point k corresponding to the end point j is between j and start point i, the equation would be

MIS(i, j) = max(MIS(i, j-1), MIS(i, k-1) + 1 + MIS(k+1, j-1))

However, MIS(k+1, j-1) will become to MIS(j, j-1) when k = j-1.
And it breaks the rule for the function MIS(a, b) that b must be larger than a.
Moreover, it may lead to overflow if it keeps going on matching the equation MIS(i, j) = MIS(i, j-1).

Solution

Don't simplify MIS(i, k-1) + MIS(k, j) into MIS(i, k-1) + 1 + MIS(k+1, j-1) and the problem(k = j-1) will be handled well while it goes recursion.