AUEB_Java_Various

DecreasingSubsequence.java

import java.util.Arrays;

/**
 *
 * @author Dedousis Dimitris <[email protected]>
 */
public class Ask2 {

    public static void main(String[] args) {
        int[] inputData = {5, 2, 8, 6, 3, 6, 9, 7, 2, 1};
        int[] decreasingSubsequence = decreasingSubsequence(inputData);
        System.out.println("The longest decreasing subsequence" + Arrays.toString(decreasingSubsequence));
    }

    /**
     * MaximumElement array is used to calculate the maximum number of nodes
     * that will be used in our result. In every iteration it holds the maximum
     * sub-sequence between the first node and the current node in the iteration.
     * For example if we have the sequence {10, 5, 3, 7, 2, 11} and we are in
     * the 2nd iteration (value 3), the 3rd element of the array gets the value
     * 3 because we have 3 nodes in the decreasing sub-sequence between values 10
     * and 3. Those nodes are {10, 5, 3}.
     *
     * Maximum Number of nodes uses is a variable that holds the biggest number
     * of the array maximumElement.
     *
     * @param inputArray
     * @return
     */
    public static int[] decreasingSubsequence(int[] inputArray) {
        int maximumElement[] = new int[inputArray.length];
        int max = -1;
        int maximunNumberOfNodesUsed = 0;
        maximumElement[0] = 1;
        for (int i = 1; i < inputArray.length; i++) {
            max = 0;
            maximumElement[i] = 0;
            for (int j = 0; j < i; j++) {
                if (inputArray[j] > inputArray[i] && maximumElement[j] > max) {
                    max = maximumElement[j];
                }
            }
            maximumElement[i] = max + 1;
            //We are keeping track of the maximum number of the nodes that they will be used in our subsequence
            if (maximumElement[i] > maximunNumberOfNodesUsed) {
                maximunNumberOfNodesUsed = maximumElement[i];
            }
        }
        System.out.println("Maximum Element array: " + Arrays.toString(maximumElement));
        System.out.printf("Length of the longest decreasing subsequence is %d \n", maximunNumberOfNodesUsed);
        //We are storing our sequence to a new array
        int[] sub = new int[maximunNumberOfNodesUsed];
        for (int i = inputArray.length - 1; i >= 0; i--) {
            if (maximumElement[i] == maximunNumberOfNodesUsed) {
                sub[maximunNumberOfNodesUsed - 1] = inputArray[i];
                maximunNumberOfNodesUsed--;
            }
        }
        return sub;
    }
}