960. Delete Columns to Make Sorted III

Version #1 DP
Find the longest non-decreasing subsequence


66.90 %
class Solution {
    public int minDeletionSize(String[] A) {
        int cols = A[0].length();
        int rows = A.length;
        int[] dp = new int[cols];
        int result = cols - 1;
        // dp[i] -> longest subsequence can form in [0, i]
        for (int col = 0; col < cols; col++) {
            dp[col] = 1;
            // check if we can connect to previous column
            for (int i = 0; i < col; i++) {
                int row = 0;
                for (row = 0; row < rows; row++) {
                    if (A[row].charAt(i) > A[row].charAt(col)) {
                        break;
                    }
                }
                if (row == rows) {
                    dp[col] = Math.max(dp[col], dp[i] + 1);
                }
            }
            result = Math.min(result, cols - dp[col]);
        }
        return result;
    }
}