SUM1007 Tổng lớn nhất

 

Để giải bài toán này ta cần biết cách duyệt qua các đường chéo song song với đường chéo chính của bảng số một cách nhanh gọn và hiệu quả. Có rất nhiều cách để thực hiện điều này. Sau đây là một cách: để ý rằng trên một đường chéo, hiệu giữa chỉ số hàng và chỉ số cột là không đổi. Hiệu này nhận giá trị từ 1-N (tương ứng với đường chéo gồm 1 ô góc trên phải (1,N)) cho đến N-1 (tương ứng với đường chéo gồm 1 ô góc dưới trái (N,1)). Do đó ta lần lượt xét các giá trị hiệu từ 1-N đến N-1. Ký hiệu giá trị này là T. Với mỗi giá trị T, ta duyệt qua các cột trên đường chéo tương ứng. Nếu T≥0 (tương ứng với các đường chéo ở nửa dưới của bảng) thì cột bắt đầu là 1 còn nếu T<0 thì cột bắt đầu là 1-T.

Đoạn lệnh sau thể hiện cách làm này:

for t:=1-n to n-1 do

       if (t>=0) then j:=1 else j:=1-t; {j là biến lưu cột bắt đầu của đường chéo}

         s:=0;                                  {tổng các phần tử trên đường chéo}

         repeat

               s:=s+a[j+t,j];                   {cộng giá trị ô hiện thời vào tổng}

               inc(j);                          {sang cột mới}

         until (j+t>n) or (j>n);         {vượt quá phạm vi của bảng}

         if (s>kq) then kq:=s;           {cập nhật kết quả}

     end;

code pascal

const

     MAXN=105;

     finp='sum.inp';

     fout='sum.out';

 

var

   n, i, j, t, s, kq: longint;

   a: array[1..MAXN, 1..MAXN] of longint;

begin

     assign(input, finp);

     reset(input);

     assign(output, fout);

     rewrite(output);

 

     readln(n);

     for i:=1 to n do

         for j:=1 to n do

             read(a[i,j]);

     kq:=-maxlongint;

     for t:=1-n to n-1 do begin

         if (t>=0) then j:=1 else j:=1-t;

         s:=0;

         repeat

               s:=s+a[j+t,j];

               inc(j);

         until (j+t>n) or (j>n);

         if (s>kq) then kq:=s;

     end;

     writeln(kq);

 

     close(input);

     close(output);

end.