You are given a two dimensional matrix M of size n*n (1 <= n <= 100) where for any i,j,(1 <= i,j <= n); Mi,j is an integer. Your task is to find a consecutive subsequence that yields the maximum sum. A consecutive subsequence can appear in a row, in a column or in a diagonal in any direction and wrapping around is also possible. For example (assume n=8) each of the following lines show a consecutive subsequence.
M2,1 M2,2 M2,3 M2,4 M2,5 M2,6 M2,7 M2,8. M2,2 M2,3 M2,4. M2,6 M2,7 M2,8 M2,1 M2,2 M4,3 M5,3 M6,3 M7,3 M1,2 M2,3 M3,4 M 4,5. M2,4 M3,3 M4,2 M5,1. M3,3 M4,2 M5,1 M1,5. M5,6. Your task is to identify a consecutive subsequence in matrix M such that sum of the elements in the subsequence will be maximal. Your program should print the length, sum of the subsequence and the subsequence itself. In case there are more than one solutions you must output only one of them. Assume that the sum does not exceed the range -32767, 32767.
The input will be a text file named seq.inp. Line 1 contains an integer n (1 <= n <= 100) corresponding to the number of rows and columns in matrix M. Line k of the input file contains a sequence of n integers, each separated by one blank, corresponding to the row k-1 of the matrix M where (2 <= k <= n+1)
The output must be a text file named seq.out. Line 1 must contain two integers, L and S corresponding to the length and sum of the subsequence found. Line k contains two integers corresponding to row index and column index, in this order, of the subsequence element k-1 where (2 <= k <= L+1).
seq.inp: 4 8 6 6 1 -3 4 0 5 4 2 1 9 1 -9 9 -2 seq.out: 3 24 3 4 4 3 1 2
CREDITS Idea: Faruk Polat Programming: Sertan Girgin Writing: Faruk Polat previous question next question Main Page