Some problems for exercise. 1 Given a sequence of numbers a1 a2 ... an stored in an array, write a program to find a subsequence of consecutive numbers ai ... aj such that the sum of numbers in the subsequence is maximized. Note that numbers may also be negative. Do the same assuming that the numbers are stored in a linked list. The output should be a linked list containing the subsequence. 2. Write a subroutine which takes a character string as input argument and returns a longest substring of the input string not containing any character more than once. Assume that the input string contains only letters and digits. 3. Write a program which reads a string of left and right brackets and checks whether they are correctly matched. Assuming the brackets are part of a Fortran format string, determine the bracket from which the rescan rule would be applied. 4. A partition of a number n into k parts is a sequence of numbers n1, n2,..,nk such that n1 + n2 + ... + nk = n and n1 >= n2 >= ... >= nk >= 1. Write a recursive and a non-recursive subroutine to generate all partitions of n into k parts. Also, generate all partitions of n, irrespective of number of parts. Define a suitable lexicographic ordering on the partitions of n and write a program to generate partitions in lexicographic order. 5. Write a non-recursive subroutine to reverse the elements of a list. You should not make a copy of the elements. 6. Let S be a set of prime numbers. A number n is said to be a S-number if all its prime factors are contained in S. Write a program which reads in a set S of prime numbers and a number n and generates the nth smallest S-number. 7. Given a linked list containing integers in nondecreasing order, write a subroutine which will remove all duplicate occurrences of integers from the list. 8. Consider a rank 2 logical array with shape (/m,n/). A false value indicates an 'empty' location while a true value indicates a 'filled' location. A particle is initially located at position (i,j). The particle can move to a neighbouring location ( one step north, south, east or west) provided that location is in the array and not filled. Write a program which reads in the array, the initial and final (empty) positions, and determines whether the particle can move from the initial to final position in the array and if so the minimum number of steps required for it to reach the final position. 9. Write generic procedures to extend the definitions of intrinsic functions like abs, sin etc. to lists of real numbers. abs(list_of_reals) should give another list containing the absolute values of reals in the original list. 10. A polynomial may be represented by a linked list with each element of the list containing one term ( coefficient and power) and a pointer to the next term. Write subroutines for operations on polynomials using this representation. When would this be better than using arrays?