1 Graded Problems
(1). You are given an integer array a[1], . . . , a[n], find the contiguous subarray (containing at least one number) which has the largest sum and only return its sum. The optimal subarray is not required to return or compute.
Taking a = [5, 4, −1, 7, 8] as an example: the subarray [5] is considered as a valid subarray with sum 5, though it only has one single element; the subarray [5, 4, −1, 7, 8] achieves the largest sum 23; on the other hand, [5, 4, 7, 8] is not a valid subarray as the numbers 4 and 7 are not contiguous.
(2). Solve Kleinberg and Tardos, Chapter 6, Exercise 10.
(3). You are given an array of positive numbers a[1], . . . , a[n].
For a sub-sequence a[i1], a[i2], . . . , a[it] of array a (that is, i1 < i2 <, . . . , < it): if it is an increasing sequence of numbers, that is, a[i1] < a[i2] < . . . < a[it], its happiness score is given by
t
k × a[ik].
k=1
Otherwise, the happiness score of this array is zero.
For example, for the input a = [22, 44, 33, 66, 55], the increasing subse-quence [22, 44, 55] has happiness score (1) × (22) + (2) × (44) + (3) ×
(55) = 275; the increasing subsequence [22, 33, 55] has happiness score
(1) × (22) + (2) × (33) + (3) × (55) = 253; the subsequence [33, 66, 55] has happiness score 0 as this sequence is not increasing.
Please design an efficient algorithm to only return the highest happiness score over all the subsequences. The optimal subsequence is not required to return or compute.
(4). You are given an m × n binary matrix g ∈ {0, 1}m×n. Each cell either contains a “0” or a “1”. Give an efficient algorithm that takes the binay matrix g, and returns the largest side length of a square that only contains 1’s. You are not required to give the optimal solution.
2 Practice Problems
(1). Given n sand piles of weights w[1], . . . , w[n] on a line, we want to merge all the sand piles together. At each step we can only merge adjacent sand piles, with cost equal to the weight of the merged sand pile. In particular, merging sand piles i and i + 1 has cost wi + wi+1. Furthermore, one gets a single sand pile of weight wi + wi+1 in its place which is now adjacent to sand piles i − 1 and i + 2. Note that different merging orders will result in
different final costs, please find the minimum cost to merge all the sand piles.
The optimal merging order is not required.
• Sample Input: n = 4, w[1, . . . , n] = [100, 1, 1, 100].
• Sample Output: the minimum cost is 1 + 1 + 2 + 100 + 102 + 100 = 306 by first merging (1, 1), then (100, 2) and (102, 100).
2
