Given an array arr of size n. Find the number of triples (i, j, k) where:
i<j<karr[i]<arr[j]<arr[k]
Example 1:
Input: arr = [1, 2, 3, 4, 5]
Output: 10
Explanation:
1. 1 2 3
2. 1 2 4
3. 1 2 5
4. 1 3 4
5. 1 3 5
6. 1 4 5
7. 2 3 4
8. 2 3 5
9. 2 4 5
10. 3 4 5Example 2:
Input: arr = [1, 2, 3, 5, 4]
Output: 7Example 3:
Input: arr = [5, 4, 3, 2, 1]
Output: 0Follow-up:
Count number of increasing subsequences in the array arr of size k.
Example 1:
Input: arr = [1, 2, 3, 4, 5], k = 4
Output: 5
Explanation:
1. 1 2 3 4
2. 1 2 3 5
3. 1 2 4 5
4. 1 3 4 5
5. 2 3 4 5Comments (27)
