算法分析
假设序列中有 $x$ 个 $1$ 和 $y$ 个 $-1$
分类讨论:
- $x=0$:这种情况很平凡,输出原序列即可
- $0 < x \leqslant y$:此时最大子段和的下界是 $1$ 并且可以达到
构造 $1$ 和 $-1$ 交替的序列后面加上剩下的 $-1$ 即可 - $x > 0$ 且 $x > y$:此时最大子段和的下界是 $x-y$
为了使-1
被充分利用,也是构造 $1$ 和 $-1$ 交替的序列后面加上剩下的 $1$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
int x = 0, y = 0;
rep(i, n) {
if (a[i] > 0) x++;
else y++;
}
if (x == 0) {
rep(i, n) cout << a[i] << " \n"[i == n-1];
}
else {
while (x and y) {
cout << 1 << ' ' << -1 << ' ';
x--; y--;
}
while (x--) cout << 1 << ' ';
while (y--) cout << -1 << ' ';
cout << '\n';
}
return 0;
}