You are given s a sequence of n integers i.E. S = s1, s2, ..., sn. Compute if it is possible to split s into two parts : s1, s2, ..., si and si+1, si+2, .., sn (0 <= i <= n) in such a way that the first part is strictly decreasing while the second is strictly increasing one
Answers
You are given s a sequence of n integers i.E. S = s1, s2, ..., sn. Compute if it is possible to split s into two parts : s1, s2, ..., si and si+1, si+2, .., sn (0 <= i <= n) in such a way that the first part is strictly decreasing while the second is strictly increasing one
Step-by-step explanation:
We will have have 3 variables : lowbound,middle,upperbound and we will begin from the middle of the array and lowbounf=0,upperbound =n-1.
We will then proceed to check with a linear passing of the array if s1,s2,...smiddle are strictly decreasing and smiddle,....,sn are strictly increasing .If affirmative, then middle is your solution.
If s1,s2,...smiddle is not strictly decreasing and smiddle,....,sn is not strictly increasing we will have no solution.
If s1,s2,...smiddle is not strictly decreasing and smiddle,....,sn is strictly increasing then:
upper bound=middle,
middle=(upper-bound+low-bound)/2 and try again.
If s1,s2,...smiddle is strictly decreasing and smiddle,....,sn is not strictly increasing then:
lowbound=middle,
middle=(upperbound+lowbound)/2 and try again.
We wil repeat the above procedure until we find a solution ,or find that there is no solution or until lowbound is equal to upperbound.
Step-by-step explanation:
A sequence <sn> is strictly increasing if:
(a) sn + 1 > sn n (b) sn + 1 > sn (c) sn + 1 = sn (d) sn + 1 = 1 answers