Question

Suppose you have an array of numbers, where each value occurs at most twice.

We consider sums of contiguous numbers in array. But we only consider such sums whose two endpoints have the similar value. The sum includes the 2 equal values themselves. So if the two equal numbers are at index i and index j (i < j) in array A, then we sum all the values A[i],A[i + 1], . . . ,A[j].

(a) Give an algorithm that finds maximum such sum. Make your algorithm as efficient as possible. Explain the algorithm briefly in English and in psuedo code.

(b) Analyze running time of your algorithm.