Algorithm: Longest Increasing Subsequence

When given an array, the algorithm to find the longest increasing subsequence is as follows:

1. Create an array 'lis' to store the length of the longest increasing subsequence ending at each index.
2. Initialize 'lis' with values of 1, as the minimum length of any subsequence is 1.
3. For each index 'i' from 1 to n-1, where 'n' is the length of the input array:
• For each index 'j' from 0 to i-1:
• If arr[i] > arr[j], update lis[i] to maximum of lis[i] and lis[j] + 1.
4. The longest increasing subsequence length will be the maximum value in the 'lis' array.

Time Complexity:

The time complexity of this algorithm is O(n^2), where 'n' is the length of the input array. This is because for each index 'i', we loop through all the indices before 'i' to find the maximum increasing subsequence length ending at that index.

Space Complexity:

The space complexity of this algorithm is O(n), as we need to create an additional array 'lis' of size 'n' to store the longest increasing subsequence length ending at each index.

Explanation:

This algorithm efficiently finds the longest increasing subsequence by dynamically updating the length of the subsequence ending at each index. By storing this information in the 'lis' array, we avoid recalculating the subsequence length for each index, resulting in an optimal solution.