最大子段和
- 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
创建日期: 2024年1月2日 19:47:42