For A[0…n−1], define Lᵢ as the longest monotonically increasing run beginning at i. Set Lₙ₋₁=1 and for earlier i, Lᵢ=1+Lᵢ₊₁ if A[i]<A[i+1], otherwise 1. Return max Lᵢ. Which is true?
Uses dynamic programming
Linear complexity using branch and bound
Nonlinear polynomial complexity using branch and bound
The recurrence reuses the solved suffix subproblem Lᵢ₊₁ while scanning backward, a dynamic-programming strategy. It takes linear time and does not use branch and bound or divide and conquer. Thus A. The recurrence computes a contiguous increasing run, despite the source’s looser word “sequence”.
More Dynamic Programming questions
GATE 2011 CS (CS1) Q48– Matrices M₁,M₂,M₃,M₄ have dimensions p×q,q×r,r×s,s×t. With p=10,q=100,r=20,s=5,t=80, find…
GATE 2010 CS (CS1) Q44– The weight of a sequence a 0,,a n-1 is a 0+a 1/2++a n-1/2n-1. Subsequences preserve order…
GATE 2026 CS (CS2) Q39– Consider a table T where the entries T[i][j], 0 i,j n, represent costs of subproblems in a…
GATE 2024 CS (CS2) Q35– Let A be an array containing integer values. The distance of A is defined as the minimum…
GATE 2024 CS (CS2) Q42– Consider an array X of n positive integers. The C code below computes the length of the…
GATE 2021 CS (CS1) Q50– Define R n to be the maximum amount earned by cutting a rod of length n meters into one or…