A Bitonic Subsequence is a part of a sequence that is formed first by increasing numbers, and after that by decreasing numbers. Write a function to return the length of the largest Bitonic subsequence from a given array of integers.
Input: int[] numbersArray = {1, 10, 5, 13, 2, 12, 7, 19, 1, 8, 4, 11, 3, 7, 5, 20}; Output: 7 Explanation: The Longest Bitonic Subsequence has length 7: 1, 5, 7, 8, 11, 7, 5. |
Solution:
1. static int longestBitonicSubsequence(int[] numbersArray) { 2. int n = numbersArray.length; 3. 4. int[] increasingSequence = new int[n]; 5. Arrays.fill(increasingSequence, 1); 6. 7. for (int i = 1; i < n; i++) { 8. for (int j = 0; j < i; j++) { 9. if (numbersArray[i] > numbersArray[j] && increasingSequence[i] < increasingSequence[j] + 1) { 10. increasingSequence[i] = increasingSequence[j] + 1; 11. } 12. } 13. } 14. 15. int[] decreasingSequence = new int[n]; 16. Arrays.fill(decreasingSequence, 1); 17. 18. for (int i = n - 2; i >= 0; i--) { 19. for (int j = n - 1; j > i; j--) { 20. if (numbersArray[i] > numbersArray[j] && decreasingSequence[i] < decreasingSequence[j] + 1) { 21. decreasingSequence[i] = decreasingSequence[j] + 1; 22. } 23. } 24. } 25. 26. return getMax(n, increasingSequence, decreasingSequence); 27. } 28. 29. private static int getMax(int n, int[] increasingSequence, int[] decreasingSequence) { 30. int max = 0; 31. for (int i = 0; i < n; i++) { 32. int maxValue = increasingSequence[i] + decreasingSequence[i] - 1; 33. max = Math.max(max, maxValue); 34. } 35. return max; 36. }