1. (20 POINTS) We w call a sequencebi,...h barely changing if neighboring number
ID: 3718993 • Letter: 1
Question
1. (20 POINTS) We w call a sequencebi,...h barely changing if neighboring numbers differ by at most 73 (that is, Wie 1, ,m-bbl S 73). Consider the following problem: INPUT: A sequence ai, OUTPUT: The length of the longest barely changing subsequence ofa, We would like to solve the problem using dynamic programming. Let Plì] = the length of the longest barely changing subsequence oti, , , , , q that ends with ai assume Give an expression (or a piece of code) that gives an efficient way of computing i 2 2)Explanation / Answer
int P[100005];
int calc( int ind) // Fucntion to perform DP , the ind gives the index of the array
{
if(P[ind]>1) // If the longest subsequence till ind is already calculated, return that value
return P[ind];
if( abs ( P[ind] - P[ind-1] ) <=73) // If the difference with the neighbour is atmost 73
P[ind] = P[ind] + P[ind-1];
if(ind==n-1) // If we have reached the end of our array
return;
calc(ind+1); // We move to the next index
}
int main()
{
// The part where the user's input is taken like the numbers and the size of array and all. Asssuming that 'n' is the size of the array
for(int i=0;i<n;i++)
P[i]=1; // Initialisation. Because the minimum length of a subsequence ending at A[i] will be 1 ( the element itself)
int ans; // To store the answer
ans=calc(1); // Calculates the answer
cout<<and<<endl; // Prints the answer
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.