cmax considers each '*' as '(', which should never be negative
cmin considers each '*' as ')' as much as possible (treat it as empty string if cmin<0 -- "max(cmin-1, 0)").
In the end, cmin should be 0. If it's larger than 0, it means even if we consider every '*' as ')', there is still some '(' left.
@roc571 No its O(n^2), check the dimensions of the dp array.
For each index of the string we can associate values for atmost n states (here n is the maximum value of the sm variable). So n^2.
Hope it helps!