Formatted question description: https://leetcode.ca/all/1395.html

# 1395. Count Number of Teams

## Level

Medium

## Description

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`

## Solution

The object of this problem is to find the number of monotone subsequences that have length 3 of the given array `rating`

. Since the length of `rating`

does not exceed 200, this problem can be solved by brute force. A solution of dynamic programming also exists.

Consider two cases, where each subsequence is monotonically increasing or monotonically decreasing. First consider the monotonically increasing case. Create an array `dp`

of length `n`

, wnere `dp[i]`

represents the number of elements in subarray `rating[0..i - 1]`

that are less than `rating[i]`

. Loop over `i`

from 1 to `n - 1`

. For each `i`

, loop over `j`

from `i - 1`

to 0. If `rating[i] > rating[j]`

, then increase `dp[i]`

by 1, and at the same time, if `dp[j] > 0`

, then there exist several elements before `j`

that are less than `rating[j]`

, so add `dp[j]`

to the number of teams. After the loop, the number of teams that are monotically increasing can be obtained.

For the monotonically decrease case, the logic is almost the same except that `rating[i] < rating[j]`

is used instead of `rating[i] > rating[j]`

.

Finally, return the number of teams of both cases.

```
class Solution {
public int numTeams(int[] rating) {
return numTeams(rating, true) + numTeams(rating, false);
}
public int numTeams(int[] rating, boolean increase) {
int teams = 0;
int length = rating.length;
int[] dp = new int[length];
for (int i = 1; i < length; i++) {
for (int j = i - 1; j >= 0; j--) {
boolean flag = increase ? rating[i] > rating[j] : rating[i] < rating[j];
if (flag) {
dp[i]++;
if (dp[j] > 0)
teams += dp[j];
}
}
}
return teams;
}
}
```