Let P[0, ..., n-1] be an array containing the varying price of a house over a period of n days: P = ...

---

Let P[0, ..., n-1] be an array containing the varying price of a house over a period of n days: P = [p_0, p_1, p_2, ..., p_(n-1)]. For every day you own the house, you have to pay a tax t on it, where t is a constant input. The profit gained from purchasing the house on day i and selling it on day j > i is p_j - p_i - t(j - i + 1). The goal is to find indices i and j > i that maximize the profit. (a) Give a divide-and-conquer algorithm to solve this problem in O(n log n) time. Do not give code. (b) Explain why the algorithm is correct. (c) Show that the running time is O(n log n).