A subsequence of a sequence of numbers a is the result of erasing zero or more elements from a. An increasing subsequence is a subsequence in which each element (except the first) is strictly greater than the previous element. An increasing subsequence of a is maximal if unerasing any of the erased elements of a does not result in a longer increasing subsequence.

For example, if a={1,3,2,6,4,5} then {1,3,4} is an increasing subsequence but not a maximal increasing subsequence. {1,2,4,5}, {1,3,4,5}, {1,2,6} and {1,3,6}, on the other hand, are maximal increasing subsequences.

You will be given a as an int[] representing a sequence of distinct numbers. Return the number of maximal increasing subsequences it contains

http://community.topcoder.com/stat?c=problem_statement&pm=7753

public class MaximalIncreasinSubsequence {

public static long findMaximalIncreasingSubsequence(int arr[]) {

int size = arr.length;

int end[] = new int[size];

end[0] = 1;

for (int i = 1; i < size; i++) {

int shadow = 0;

int sum = 0;

for (int j = i - 1; j >= 0; j--) {

if (arr[j] > shadow && arr[j] < arr[i]) {

shadow = arr[j];

sum = sum + end[j];

}

}

if (sum == 0)

sum = 1;

end[i] = sum;

}

long finalanswer = 0;

int max = 0;

for (int i = size - 1; i >= 0; i--) {

if (max < arr[i]) {

finalanswer = finalanswer + end[i];

max = arr[i];

}

}

return finalanswer;

}

public static void main(String[] args) {

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

int b[] = {564,234,34,4365,424,2234,306,21,934,592,195,2395,2396,29345,13295423,23945,2};

System.out.println("Maximal Increasing subsequence"+findMaximalIncreasingSubsequence(arr));

System.out.println("Maximal Increasing subsequence"+findMaximalIncreasingSubsequence(b));

}

}

## No comments:

Post a Comment