ALGORITHM PROBLEM:

A) Significant Inversions: We are given a sequence of n arbitrary but distinct real numbers . We define a significant inversion to be a pair i < j such that ai > 2 aj . Design and analyze an O(n log n) time algorithm to count the number of significant inversions in the given sequence.

[Hint: Use divide-&-conquer. Do the combine step carefully]

B) The Maximum-Sum Monotone Sub-Array Problem: Input: An array A[1..n] of arbitrary positive integers. Output: The maximum-element-sum contiguous sub-array of A[1..n] whose entries form a monotone sequence (either ascending or descending)

[Hint: Use an incremental approach]