列の塗り方を決めたとき、各行について、まだ塗られていないマスの和が0以上なら塗り、そうでないとき塗らないのが最適です。

よって列の塗り方を全探索することで \(O(2^WHW)\) でこの問題を解くことができます。

以下の実装例では、列の塗り方を「列 \(i\) を塗ることと、 s の \(i\) bit 目が \(1\) であることが同値」となるような整数変数 s を用いて表しています。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int h, w;
  cin >> h >> w;
  vector<vector<int>>a(h, vector<int>(w));
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      cin >> a[i][j];
    }
  }

  long long ans = 0;
  for(int s=0; s<1<<w; s++){
    long long crr = 0;  // すでに塗られているマスの和
    for(int i=0; i<h; i++){
      long long temp = 0;  // 行 i でまだ塗られていないマスの和
      for(int j=0; j<w; j++){
        if((s>>j) & 1){
          crr += a[i][j];
        }else{
          temp += a[i][j];
        }
      }
      if(temp > 0){
        crr += temp;
      }
    }
    ans = max(ans, crr);
  }
  cout << ans << endl;
}

実装例 (Python)

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

ans = 0
for s in range(1<<W):
  crr = 0  # すでに塗られているマスの和
  for i in range(H):
    temp = 0  # 行 i でまだ塗られていないマスの和
    for j in range(W):
      if (s>>j) & 1:
        crr += A[i][j]
      else:
        temp += A[i][j]
    if temp > 0:
      crr += temp
  ans = max(ans, crr)
print(ans)

なお、再帰関数を用いるなど、適切な実装により、計算量を \(O(2^{\min(H,W)} \max(H,W))\) とすることもできます。

実装例 (Python)

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

if W > H:
  # 転置
  A = list(zip(*A))
  H, W = W, H

# S[i] = 行 i のうちまだ塗られていないマスの和
S = [sum(a) for a in A]

def f(j, crr):
  if j == W:
    return crr + sum(max(0, s) for s in S)

  # 列 j を選ばない
  ans = f(j+1, crr)

  # 列 j を選ぶ
  for i in range(H):
    S[i] -= A[i][j]
    crr += A[i][j]
  ans = max(ans, f(j+1, crr))
  for i in range(H):
    S[i] += A[i][j]
    crr -= A[i][j]

  return ans

print(f(0, 0))