Advertisement
Guest User

Untitled

a guest
Feb 20th, 2020
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8.     int n, m;
  9.  
  10.     cin >> n >> m;
  11.     vector<vector<int>> array(n, vector<int>(m, 0));
  12.  
  13.     for (int i = 0; i < n; i++)
  14.         for (int j = 0; j < m; j++) {
  15.             cin >> array[i][j];
  16.             if (array[i][j] == 0)
  17.                 array[i][j] = -1000;
  18.         }
  19.  
  20.     int ans = 0x80000000;
  21.  
  22.     for (int i = 0; i < n; i++) {
  23.         vector<int> dp(m, 0);
  24.         // 壓縮二維陣列(把 i ~ n 的陣列壓成一維)
  25.         // 就可以當作最大連續和(一維)問題計算
  26.         for (int j = i; j < n; j++) {
  27.             int sum_now = 0;
  28.  
  29.             for (int k = 0; k < m; k++) {
  30.                 dp[k] += array[j][k];
  31.  
  32.                 // 當前和 >=0,那就試著加入下一個
  33.                 if (sum_now >= 0)
  34.                     sum_now += dp[k];
  35.                 // 當前和<0,那就當作第一個重新開始
  36.                 else
  37.                     sum_now = dp[k];
  38.  
  39.                 ans = max(sum_now, ans);
  40.             }
  41.         }
  42.     }
  43.  
  44.     cout << max(ans, 0) << "\n";
  45.     return 0;
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement