Disjoint subsequences in an array with maximum difference - PrismoSkills
Problem: Find two disjoint (non-overlapping) subsequences in an array with maximum difference.
Solution: This is an extended case of Kadane's algorithm and previous problem.
Only difference is that in the previous problem, the contiguous subsequences could be overlapping but they cannot be in this case.
For every index in the array, computer max and min subsequences on either side of the index.
Find the difference between max-min pairs of these 4 subsequences and choose the max among them.
Read full article from Disjoint subsequences in an array with maximum difference - PrismoSkills
Problem: Find two disjoint (non-overlapping) subsequences in an array with maximum difference.
Solution: This is an extended case of Kadane's algorithm and previous problem.
Only difference is that in the previous problem, the contiguous subsequences could be overlapping but they cannot be in this case.
For every index in the array, computer max and min subsequences on either side of the index.
Find the difference between max-min pairs of these 4 subsequences and choose the max among them.
Read full article from Disjoint subsequences in an array with maximum difference - PrismoSkills