最大子段和

  • 1d
int MaxSum(const std::vector<int>& a) {
    int n = a.size();
    int sum = 0, b = 0;
    for (int i = 0; i < n; ++i) {
        if (b > 0) {
            b += a[i];
        } else {
            b = a[i];
        }
        sum = std::max(sum, b);
    }
    return sum;
}
  • 2d
int MaxSum(const std::vector<std::vector<int>>& a) {
    int m = a.size(), n = a[0].size();
    int sum = 0;
    for (int i = 0; i < m; ++i) {
        std::vector<int> b(n);
        for (int j = i; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                b[k] += a[j][k];
            }
            sum = std::max(sum, MaxSum(t));
        }
    }
    return sum;
}

最后更新: 2024年1月2日 21:37:12
创建日期: 2024年1月2日 19:47:42
回到页面顶部