Write a method void maxSub(int[] a, out int start, out int
end) that takes an array a of integers that may be
positive, negative, or zero. The method should find the contiguous
subarray in a with a maximal sum, and returns the
indices of the start and end of the subarray.
Hint: Let L[i] be the maximum sum of any contiguous subarray that ends at position i (including the empty array, whose sum is 0). If you know L[i - 1], you can compute L[i].
Modify the longest palindromic subsequence method from lecture to return the longest contiguous palindromic substring of a string s.
Write a method that returns the longest common subsequence of two strings s and t, where a subsequence is not necessarily contiguous.
Modify the Dragon's Den homework exercise for the situation in which the treasure mound contains only a single instance of each treasure.
Hint: The original Dragon's Den was a one-dimensional dynamic programming problem, but with this change it becomes two-dimensional. Suppose there are N treasures, listed in some order. For each possible amount of weight k and value i ≤ N, let V[k, i] be the maximum value of a bag of treasure whose total weight is <= k and which contains only treasures from the first i treasures in the list. Then for example, V[k, 0] = 0 for all k. If you know V[k, i - 1] for all k, you can compute V[k, i] for any k.
Write a method that takes a square matrix a[,] containing only 0s
and 1s. The method should return the offset and size of the largest
square submatrix of a that contains only 1s.