Find the greatest difference of two values in an array such that for the pair (a

Question

Find the greatest difference of two values in an array such that for the pair (a[i], a[j]), i < j and a[i] > a[j].
Ex: [11, 7, 17, 2] would have a greatest difference of 15 coming from the pair (17, 2).
(a) Design a divide and conquer algorithm that finds the greatest difference in the array in O(nlogn) time.

(b) Design a dynamic programming solution that finds the greatest difference in the array in O(n) time. Find the greatest difference of two values in an array such that for the pair (a[i], a[j]), i < j and a[i] > a[j].
Ex: [11, 7, 17, 2] would have a greatest difference of 15 coming from the pair (17, 2).
(a) Design a divide and conquer algorithm that finds the greatest difference in the array in O(nlogn) time.

(b) Design a dynamic programming solution that finds the greatest difference in the array in O(n) time.
Ex: [11, 7, 17, 2] would have a greatest difference of 15 coming from the pair (17, 2).
(a) Design a divide and conquer algorithm that finds the greatest difference in the array in O(nlogn) time.

(b) Design a dynamic programming solution that finds the greatest difference in the array in O(n) time.

Explanation / Answer

def get_max_daq(alist, currmax):
    if(len(alist)==1):
        return max(alist[0], currmax)
    else:
        currmax = max(alist[0], currmax)
        return get_max_daq(alist[1:], currmax)

def get_min_daq(alist, currmin):
    if(len(alist)==1):
        return min(alist[0], currmin)
    else:
        currmin = min(alist[0], currmin)
        return get_min_daq(alist[1:], currmin)

def divide_and_conquer(alist):
    maxnum = get_max_daq(alist, float('-inf'))
    minnum = get_min_daq(alist, float('inf'))
    return maxnum-minnum

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.