How about brute force?  This consists of $O(n^3)$ steps in your case.