[Java] DP O(N^2)
asc[i][j]: number of ASC sequence with len i end at rating[j]\ndesc[i][j]: number of DESC sequence with len i end at rating[j]\n\nBase Case\nasc[1][j]= 1, desc[
`asc[i][j]`: number of ASC sequence with `len i` end at `rating[j]`\n`desc[i][j]`: number of DESC sequence with `len i` end at `rating[j]`\n\n**Base Case**\nasc[1][j]= 1, desc[1][j] = 1 for 0 <= j < n\n\n**Calculate 2 <= i <= 3**\nasc[i][j] = sum(asc[i-1][k]) where 0 <= k < j && rating[k] < rating[r]\ndesc[i][j] = sum(desc[i-1][k]) where 0 <= k < j && rating[k] > rating[r]\n\n\nthe answer will be sum of asc[3][j] + desc[3][j] for 0 <= j < n\ncan do the summing up during i == 3 for speedup\n\n```\nclass Solution {\n    public int numTeams(int[] rating) {\n        final int n  = rating.length;\n        int[][] asc = new int[4][n];\n        int[][] desc = new int[4][n];\n        for (int i = 0; i < n; i++) {\n            asc[1][i] = 1;\n            desc[1][i] = 1;\n        }\n        int ret = 0;\n        for (int i = 2; i <= 3; i++) {\n            for (int r = 1; r < n; r++) {\n                for (int l = 0; l < r; l++) {\n                    if (rating[l] < rating[r])\n                        asc[i][r] += asc[i-1][l];\n                    if (rating[l] > rating[r])\n                        desc[i][r] += desc[i-1][l];\n                }\n                if (i == 3)\n                    ret += asc[i][r] + desc[i][r];\n            }\n            \n        }\n        return ret;\n    }\n}\n```
[]