Nerde Nolzda

UVa108: Maximum Sum

先建立一個陣列 sumArr,使 sumArr[i][j + 1] = arr[i][0] + arr[i][1] + ... + arr[i][j]。換句話說,sumArr[i][j + 1] 是第 i 行 [0, j] 列的和,而 sumArr[k][j] - sumArr[k][i] 便是第 k 行 [i, j] 列的和。如此便能夠將問題轉化為求 i * j 個一維陣列的最大區段和,時間複雜度為 O(n^3)

Let sumArr[i][j + 1] = arr[i][0] + arr[i][1] + ... + arr[i][j]. Thus, sumArr[i][j + 1] is the sum of rows [0, j] in column i, and sumArr[k][j] - sumArr[k][i] is the sum of rows [i, j] in column k. This way, the problem can be simplified to finding the maximum subsequence in i * j 1D-arrays, making the time complexity O(n^3).

UVa Link

#include <iostream>

int main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);
  int n, arr[100][100], sumArr[100][101] = { 0 };
  while (std::cin >> n) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        int in;
        std::cin >> in;
        arr[i][j] = in;
        sumArr[i][j + 1] = sumArr[i][j] + in;
      }
    }
    int max = -100000;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j <= n; j++) {
        int sum = 0;
        for (int k = 0; k < n; k++) {
          sum += sumArr[k][j] - sumArr[k][i];
          if (sum > max) max = sum;
          if (sum < 0) sum = 0;
        }
      }
    }
    std::cout << max << '\n';
  }
}

Related Posts

0 comments

Post a comment

Send an email to comment@nerde.pw.