Homework 6.
Due, Wednesday, November 10 in lecture

Each of the problems below asks you to devise a recursive
method or algorithm. For each one, give a recurrence relations
that describes its running time.

Goodrich and Tamassia P. 97-99

Problems C-2.5
    Write a short Java method that finds the minimum and
    maximum values in an array of int values without using
    any loops.
C-2.6
    Write a short recursive Java methods that will check if an
    array of int values has any repeated entries.
C-2.9
   Write a short recursive Java method that determines if a string
    s is a palindrome, that is, it is equal to its reverse.
    "racecar" and gohangasalamiimalasagnahog" are palindromes.

When we discussed O-notation, we discussed a problem called
the maximum consiguous subsequence sum problem which,
given an array of integers a, finds the two indices i and j
such that a[i] + a[i+1] +...+ a[j] is maximum.
(If j < i, then the subsequence is empty and the sum is 0).

Devise a divide-and-conquer algorithm to solve this problem
and write it up as a Java method.
A rough outline of the algorithm will go as follows:

Divide the array into two halves.
Solve the problem recursive on both halves.
Find a linear time algorithm that finds the maximum
  over all subsequences that span the boundary beterrn the 
  two halves.
Find and return the largest sum over all the results from the
  two halves and the subsequences that span the middle.