Java O(N^2) Very Simple 1D DP, 2 Pass
So basically we are employing the same technique as largest increasing/decreasing subsequence DP problem. For ith, we go back from i-1 to 0 and see how many ele
So basically we are employing the same technique as largest increasing/decreasing subsequence DP problem. For `ith`, we go back from `i-1` to `0` and see how many elements is `rating[i]` greater than, and we add the `DP[j]` to `count` for all `j < i` such that `rating[i] > rating[j]`. Why? Because we know that `rating[j]` is less than `rating[i]` and we also know that `rating[j]` is greater than `DP[j]` elements on it\'s left so they are also less than `rating[i]` hence they can form a combination. \n\nSimilarly we look for all `j < i` such that `rating[i] < rating[j]` during second pass for `rating[i] > rating[j] > rating[k]` combo.\n\n`DP[i]` is count of ratings less than `rating[i]` on it\'s left in first pass and count of ratings greater than `rating[i]` in second pass. Our answer is `count + DP[j]` for all `j < i` so that `rating[i] > rating[j]` during first pass and `rating[i] < rating[j]` during second pass.\n\nI have started my `j` loop at `i` because there are no duplicates hence for `j == i` nothing is gonna happen. It saved me trouble of checking `>=0` index check.\n```\nclass Solution {\n    public int numTeams(int[] rating) {\n        if(rating == null || rating.length == 0){\n            return 0;\n        }\n        \n        int len = rating.length;\n        int[] dp = new int[len];\n        int count = 0;\n        \n        // first <r[i] <r[j] <r[k] order\n        for(int i = 0; i < len; i++){\n            for(int j = i; j >= 0; j--){\n                if(rating[i] > rating[j]){\n                    dp[i]++;\n                    count = count + dp[j];\n                }\n            }\n        }\n        \n        //System.out.println(count);\n        dp = new int[len];\n        \n        for(int i = 0; i < len; i++){\n            for(int j = i; j >= 0; j--){\n                if(rating[i] < rating[j]){\n                    dp[i]++;\n                    count = count + dp[j];\n                }\n            }\n        }\n        \n        return count;\n        \n    }\n}\n```
['Dynamic Programming', 'Java']