二维矩阵子集的最大值

登录—专业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,4
	ll ans5 = std::max(ans1 * ans2, ans1 * ans4);
	ans5 = std::max(ans5, ans3 * ans4);
	ans5 = std::max(ans5, ans3 * ans2);

排列组合求最大值