Programming Assignment 3 - Maximal Array Samples

Introduction to Computer Science II, Summer 2001

Due Date
Background
The Problem
Testing

Due Date

This assignment is due on Tuesday, 3 July, no later than 2:00 p.m.

See the assignment turn-in page for instructions on turning in your assignment.

Background

Let A be an array of N integers, N >= 0. A sample of A is a consecutive sequence of elements from A, every one of which contains a value different from every other value in the sequence. The size of a sample is the number of values in the sample.

For example, given the array

{ 1, 2, 3, 1, 2, 4, 6 }

then { 1, 2, 3 } is a sample of size 3 and { 3, 1, 2, 4 } is a sample of size 4. { 2, 3, 1, 2 } is not a sample because the value 2 is repeated.

A maximal sample is a sample of an array that is at least as large as any other sample of the array. In the previous example, { 3, 1, 2, 4, 6 } is a maximal array sample. An array may have more than one maximal sample; for example the array

{ 1, 2, 3, 3, 3, 2, 1 }

has the maximal samples { 1, 2, 3 } and { 3, 2, 1 }.

The Problem

Write a procedure with the prototype

sample find_maximal_sample(const int a[], int a_size);

that returns a maximal sample from the input array a containing a_size integers. If a contains more than one maximal sample, find_maximal_sample() can return any of them.

Testing

The file mas.h contains the prototype for find_maximal_sample() and the definition for sample. You can compile your procedure source with the file test-mas.o to test your code. You can download mas.h and test-mas.o from a browser (shift-left-click on the link) or access them directly from the directory


/export/home/us/csfac/cs176-summer2001/pa/3

from any PC lab machine running linux or from rockhopper.