CS 124 Section 4 Solutions
Haneul Shin February 2021
1. Given an array a with n integers, design a divide and conquer algorithm to find the sum of the maximum sum subarray. This is a subarray with the maximum possible sum, which may be empty. For instance, for a = [2, 3, -7, 1, 5, -3], the maximum subarray sum is 6.
Solution. We can construct a divide and conquer algorithm that does the following:
• Divide the array into two equally sized subarrays l = a[0, n/2 − 1] and r = a[n/2, n − 1]. • Recursively compute the maximum subarray sum of l.
• Recursively compute the maximum subarray sum of r.
• Find the maximum subarray sum that crosses the divide between l and r.
– Iteratively find i that maximizes the subarray sum of a[i, n/2 − 1]. – Iterately find j that maximizes the subarray sum of a[n/2,j].
– Add the two sums.
• Return the maximum of the above three sums.
The time complexity of this solution is given by the recurrence T (n) = 2T (n/2) + O(n), so
T (n) = O(n log n).
2. Given an array a with n integers, find the length of a longest increasing subsequence of the array. (This is a maximum-length subsequence of the array such that each element is strictly larger than the previous element.)
Solution. We use dynamic programming. Let length[k] be the length of the longest increasing subsequence that ends at index k. Then, our DP relation is
length[k] = max max length[i] + 1, 1 i|i