#UVa:108-Maximum Sum

灆洢 2012-03-14 17:35:24

先建立一個存sum的二維陣列,此sum為該行第一列加到該列的數值。(Ex. sum[2][5] = array[0][5] + array[1][5] + array[2][5])當建完這個陣列後,要求array[i…j]k就可以很容易算出來。接著窮舉所有第i列到第j列的所有可能性,對於每一次窮舉皆可當作是array[i…j][k]以k為其index的一個一維陣列,利用這個一維陣列算出所有可能性的其最大連續和即是答案。

C++(0.036)

/*******************************************************/
/* UVa 108 Maximum Sum                                 */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2012/03/14                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
#include<climits>
using namespace std;

int main(){
  int N;
  int array[105][105];
  int max_sum, sum;
  while( scanf( "%d", &N ) != EOF ){
    for( int i = 1 ; i <= N ; i++ )
      for( int j = 1 ; j <= N ; j++ )
        scanf( "%d", &array[i][j] );

    int column_array[105][105] = {0};
    for( int i = 1 ; i <= N ; i++ )
      for( int j = 1 ; j <= N ; j++ )
        column_array[i][j] = column_array[i-1][j] + array[i][j];

    max_sum = INT_MIN;
    for( int i = 1 ; i <= N ; i++ )
      for( int j = i ; j <= N ; j++ ){
        sum = 0;
        for( int k = 1 ; k <= N ; k++ ){
          sum += column_array[j][k] - column_array[i-1][k];
          if( sum > max_sum ) max_sum = sum;
          if( sum < 0 ) sum = 0;
        }
      }
    printf( "%d\n", max_sum );
  }
  return 0;
}

在〈“#UVa:108-Maximum Sum”〉中有 2 則留言

  1. Howard表示:

    if( sum < 0 ) sum = 0;
    為甚麼要加這行

    • 灆洢表示:

      表示從前一次的行數到第k行之間的總和已成為負數,故重新從第k+1行當作起點開始計算總和。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料