CODEWITHSUNDEEP
algorithmdynamic-programminggreedy
user3070752
user3070752

Reputation: 734

what is the greedy or dynamic programming approach of this?

we have a sequence of REAL numbers.all of the numbers are unique.we want to have an ascending sequence by changing some of these values.we are allowed to change any arbitrary numbers.how to find the optimum algorithm to determine the minimum number of necessary changes to make this sequence? we can use greedy or dynamic programming approach.

Upvotes: 1

Views: 91

Answers (1)

Herokiller
Herokiller

Reputation: 2991

first find longest increasing subsequence http://en.wikipedia.org/wiki/Longest_increasing_subsequence

then change all numbers which do not belong to this subsequence to fit the rule

(proof: if we change less numbers and acquire ascending sequence, then the numbers which were not changed were initially forming increasing subsequence longer then 'longest')

Upvotes: 1

Related Questions