1395. Count Number of Teams

https://leetcode.com/problems/count-number-of-teams/

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

• Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).

• A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

Constraints:

• n == rating.length

• 1 <= n <= 200

• 1 <= rating[i] <= 10^5

找数组中长度为3的递增序列和递减序列的总数。increasing subseq => DP。当遍历到i时，nums[i]会作为序列尾（第三个元素），需要对前面的j的已有结果，也就是序列长度为2的，做遍历，因此dp[j]存以nums[j]为递增（减）序列第二个位置时序列的个数。i每次能和前面j拼在一起时，res += dp[j]。

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        dp_g, dp_l = [0] * n, [0] * n
        res = 0
        for i, r in enumerate(rating):
            for j in range(i):
                if r > rating[j]:
                    dp_g[i] += 1
                    res += dp_g[j]
                elif r < rating[j]:
                    dp_l[i] += 1
                    res += dp_l[j]
        return res