Solution
Approach 1: Mathematical
Intuition
Let's try to count the number of subsequences with minimum A[i]
and maximum A[j]
.
Algorithm
We can sort the array as it doesn't change the answer. After sorting the array, this allows us to know that the number of subsequences with minimum A[i]
and maximum A[j]
is . Hence, the desired answer is:
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: , the space used by
pow2
. (We can improve this to space by calculating these powers on the fly.)
Analysis written by: @awice.