二维矩阵子集的最大值

登录—专业IT笔试面试备考平台_牛客网

正好遇到了

对于一维,我们只需要贪一次

int ans = -1E9;
int suf = -1E9;
for (int i = 0; i < n; i++) {if (i && (a[i] - a[i - 1]) % 2 == 0) {suf = 0;}suf = std::max(suf, 0) + a[i];ans = std::max(ans, suf);
}

ans就是最大值.

对于二维我们要把这个公式用四次

    ll res1 = -1e9, ans1 = -1e9;for (int i = 0; i < n; i++) {res1 = std::max(0LL, res1)+a[i];ans1 = std::max(ans1, res1);}ll res2 = -1e9, ans2 = -1e9;for (int i = 0; i < m; i++) {res2 = std::max(0LL, res2) + b[i];ans2 = std::max(ans2, res2);}ll res3 = 1e9, ans3 = 1e9;for (int i = 0; i < n; i++) {res3 = std::min(0LL, res3) + a[i];ans3 = std::min(res3, ans3);}ll res4 = 1e9, ans4 = 1e9;for (int i = 0; i < m; i++) {res4 = std::min(0LL, res4) + b[i];ans4 = std::min(res4, ans4);}//1,3是a,2,4是b,1,2,1,4,3,2,3,4ll ans5 = std::max(ans1 * ans2, ans1 * ans4);ans5 = std::max(ans5, ans3 * ans4);ans5 = std::max(ans5, ans3 * ans2);

排列组合求最大值