A subsequence of sequence A is a sequence that is obtained from A by removing several (zero or more) elements from it. Eg: {1,3,5}, {2,4},{ } are subsequence of sequence {1,2,3,4,5}.
An arithmetic subsequence of sequence A is a subsequence of A , that is an arithmetic progression. Eg: {1,3,5}, {1,2,3} are arithmetic subsequence of sequence {1,2,3,4,5} with length 3.
how to construct any permutation of first N positive integers such that the length of the longest arithmetic subsequence of the permutation is equal to K.
For example if N=5 and K=3, Different permutation will be N! ie, 5!=120 ways to represent first N positive numbers.
Now our answer will be any one permutation which will be having longest arithmetic subsequence in it of length K.
For example if N=5 and K=3 one of the many permutation will be {4,1,3,2,5} because in this sequence {4,3,2} & {1,3,5} are two arithmetic subsequence with length 3 and no other arithmetic subsequence with length > K is present here.
We can not take {4,5,3,2,1} as our answer because it is having {4,3,2,1} as its longest arithmetic subsequence which is exceeded the given limit K=3 . So we not consider it as our answer.
We just need any permutation which satisfies our given conditions.
For eg. If N=5 and K=3 then following can be valid permutations for our answer : {4,1,3,2,5} {2,3,5,1,4} {1,2,5,4,3}... Etc...
One obvious approach is to generate all permutations and then to compute the Longest AP Sequence and check if is equal to given length and print that permutation but it would be O(n! * n^2) which will be too large. I even tried observing some pattern but couldn't come up with any observation.