Length of longest increasing absolute even subsequence in Java

The Length of the Longest Increasing Absolute Even Subsequence is a mathematical problem that connects mathematics, algorithms, and computer science. It involves determining the longest subsequence of numbers in which each element is strictly greater than its predecessor in absolute value and even. 

Example1 :

Input: arr[] = {1, -3, 2, 3, -4, 6, -8, -2, 4}

Output: 4

Explanation: The input array contains both positive and negative integers. The longest increasing absolute even subsequence is {2, 6, -8, 4}, which has a length of 4. The subsequence consists of even numbers arranged in increasing order of their absolute values.

Example2 :

Input: arr[] = {10, 22, 9, 33, 21, 50, 41, 60} 

Output: 4

Explanation: The input array consists of only positive integers. In the above case, the subsequence {10, 22, 50, 60} has the highest length of 4.

Using Naive Approach

Algorithm

Step 1: Initialize a sequence with length n.

Step 2: Set a variable maxLen to track maximum length.

Step 3: Iterate through each element in the input array arr.

Step 4: Set dp[i] to 1 for a subsequence of length 1.

Step 5: Iterate through all elements before i.

Step 6: Check if a current element can be added to the subsequence.

Step 7: Update dp[i] to a maximum of the current value and dp[j] + 1.

Step 8: Update maxLen to the maximum value between maxLen and dp[i].

Step 9: Return maxLen as the longest increasing absolute even subsequence.

Here is an implementation of finding the length of the longest increasing absolute even subsequence using a naive approach :

FileName:LongestIncreasingAbsoluteEvenSubsequence.java

public class LongestIncreasingAbsoluteEvenSubsequence {

    public static int longestIncreasingAbsoluteEvenSubsequence(int[] arr) {

        int n = arr.length;

        int[] dp = new int[n]; 

        int maxLen = 0; 

        // Iterate through each element in the array

        for (int i = 0; i < n; i++) {

            dp[i] = 1; 

            // Iterate through all previous elements to check if they can be added to the subsequence ending at arr[i]

            for (int j = 0; j < i; j++) {

                // Check if a current element can be added to the subsequence ending at arr[i]

                if (arr[i] != arr[j] && Math.abs(arr[i]) > Math.abs(arr[j]) && arr[i] % 2 == 0 && arr[j] % 2 == 0) {

                    dp[i] = Math.max(dp[i], dp[j] + 1); // Update the length of the longest increasing absolute even subsequence ending at arr[i]

                }

            }

            maxLen = Math.max(maxLen, dp[i]);

        }

        return maxLen; 

    }

    public static void main(String[] args) {

        int[] arr = {1, -3, 2, 3, -4, 6, -8, -2, 4}; 

        int length = longestIncreasingAbsoluteEvenSubsequence(arr);

        System.out.println("Length of longest increasing absolute even subsequence: " + length);

    }

}

Output: 

Length of longest increasing absolute even subsequence: 4

Complexity analysis: The above approach's time complexity is O(n^2) due to a nested loop proportional to the input size n, and its space complexity is O(n) due to the additional space required for the dynamic programming array.

Using Optimized Approach

Algorithm

Step1: Create an ArrayList for increasing absolute even subsequence.

Step 2: Iterate through each element in the input array.

Step 3: Check if the element is even and calculate the absolute value of the even element.

Step 4: Perform a binary search on the ArrayList to find the insertion point.

Step 5: Adjust the index if the negative value returns.

Step 6: Add absolute value to the end of the list if the index equals the ArrayList size.

Step 7: Update index value with absolute value.

Step 8: Return ArrayList size as the length of the longest increasing absolute even subsequence.

Here is an implementation of finding the length of the longest increasing absolute even subsequence using an optimized approach :

FileName:LongestIncreasingAbsoluteEvenSubsequence1.java

import java.util.*;

public class LongestIncreasingAbsoluteEvenSubsequence1 {

    public static int longestIncreasingAbsoluteEvenSubsequence(int[] arr) {

        // Filter even numbers and sort them based on their absolute values

        ArrayList lis = new ArrayList<>();

        for (int num : arr) {

            if (num % 2 == 0) {

                int absNum = Math.abs(num);

                int index = Collections.binarySearch(lis, absNum);

                if (index < 0) index = -(index + 1);

                if (index == lis.size()) lis.add(absNum);

                else lis.set(index, absNum);

            }

        }

        return lis.size();

    }

    public static void main(String[] args) {

        int[] arr = {1, -3, 2, 3, -4, 6, -8, -2, 4}; 

        int length = longestIncreasingAbsoluteEvenSubsequence(arr);

        System.out.println("Length of longest increasing absolute even subsequence: " + length);

    }

}

Output:

Length of longest increasing absolute even subsequence: 4

Complexity analysis: The above approach has a time complexity of O(n log n) due to binary search operations on the input array and a space complexity of O(n) due to the additional space needed to store the sorted list, which can contain up to n elements.