702720. Count Increasing Subsequences
Count Increasing Subsequences
Summary
The problem is to count the number of increasing subsequences in a given array. An increasing subsequence is a sequence of elements where each element is greater than the previous one. The goal is to find all such subsequences and count them.
Detailed Explanation
To solve this problem, we can use dynamic programming. We will maintain an array dp where dp[i] represents the number of increasing subsequences ending at index i. Initially, dp[0] = 1, because a single element is always considered as an increasing subsequence.
Then, for each element arr[i], we iterate through all previous elements j < i. If arr[j] < arr[i], it means that the subsequence ending at i can be extended by adding the current element. In this case, we update dp[i] as the sum of dp[j] and 1 (the new increasing subsequence).
Here is a step-by-step breakdown:
- Initialize an array
dpwith the same length as the input array. - Set
dp[0] = 1. - Iterate through each element
arr[i]in the array:- For each previous element
j < i, check ifarr[j] < arr[i]. - If true, update
dp[i]asdp[i] + dp[j] + 1. This represents the new increasing subsequence ending ati.
- For each previous element
- Return the sum of all elements in
dparray.
Time complexity: O(n^2), where n is the length of the input array. Space complexity: O(n).
Here is an ASCII art diagram to illustrate the algorithm:
+-----------+
| arr[0] |
+-----------+
|
v
+---------------+---------------+
| dp[1] = 1 | dp[2] = ? |
+---------------+---------------+
|
v
+---------------+---------------+
| dp[3] = ? | dp[4] = ? |
+---------------+---------------+
|
v
+-----------+
| arr[n-1] |
+-----------+
Optimized Solutions
Java
public class Main {
public static int countIncreasingSubsequences(int[] arr) {
int n = arr.length;
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] += dp[j];
}
}
}
int count = 0;
for (int i : dp) {
count += i;
}
return count;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
System.out.println(countIncreasingSubsequences(arr));
}
}