Given a non-negative integer array A[1..n] (that is, A contains numbers from the set {0, 1,...

 

Transcribed Image Text:

Given a non-negative integer array A[1..n] (that is, A contains numbers from the set {0, 1, 2, 3, 4, ...}), the next smaller value of A (NSVA) is an integer array of length n, where NSVA[i], 1 ≤ i ≤n, is defined as follows: 1. if A[i]=0 then NSVA[i] = 0 2. otherwise, NSVA[i] = j, where (a) for every h E [1..j-1], A[i] ≤ A[i+h], and (b) either i + j= n+1 or A[i] > A[i + j]. In short, NSV[i] shows how far one should trace forward from A[i] to reach a smaller value than A[i]. Write an algorithm to compute the NSV array in O(n) time, using the stack data structure. Below is an example of an NSV array. [6 marks] i A 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 01 3 3 7 7 15 5 0 NSVA 0 8 4 3 2 1 3 2 1 0 2 2 6 6 0 4 4 4 3 2 1 0 2 1 Given a non-negative integer array A[1..n] (that is, A contains numbers from the set {0, 1, 2, 3, 4, ...}), the next smaller value of A (NSVA) is an integer array of length n, where NSVA[i], 1 ≤ i ≤n, is defined as follows: 1. if A[i]=0 then NSVA[i] = 0 2. otherwise, NSVA[i] = j, where (a) for every h E [1..j-1], A[i] ≤ A[i+h], and (b) either i + j= n+1 or A[i] > A[i + j]. In short, NSV[i] shows how far one should trace forward from A[i] to reach a smaller value than A[i]. Write an algorithm to compute the NSV array in O(n) time, using the stack data structure. Below is an example of an NSV array. [6 marks] i A 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 01 3 3 7 7 15 5 0 NSVA 0 8 4 3 2 1 3 2 1 0 2 2 6 6 0 4 4 4 3 2 1 0 2 1

Answer rating: 100% (QA)

Heres an algorithm in Python to compute the NSVA a... View the full answer