//k項までの{最小, 最大}が分かっていれば, k+1項までの{最小, 最大}を計算できる. {}の中が同じなので, 最小と最大を持ってDPできそう。 #include #include #define int long long using namespace std; int INF = 1e+16; int n; int a[16]; int dp[17][2]; signed main() { int i, j; cin >> n; for (i = 0; i < n; i++) cin >> a[i]; for (i = 0; i <= n; i++) { dp[i][0] = INF; dp[i][1] = -INF; } dp[0][0] = 0; for (i = 0; i < n; i++) { for (j = 0; j < 2; j++) { if (dp[i][j] == INF || dp[i][j] == -INF) continue; dp[i + 1][0] = min(dp[i + 1][0], dp[i][j] + a[i]); dp[i + 1][1] = max(dp[i + 1][1], dp[i][j] + a[i]); dp[i + 1][0] = min(dp[i + 1][0], dp[i][j] - a[i]); dp[i + 1][1] = max(dp[i + 1][1], dp[i][j] - a[i]); dp[i + 1][0] = min(dp[i + 1][0], dp[i][j] * a[i]); dp[i + 1][1] = max(dp[i + 1][1], dp[i][j] * a[i]); if (a[i] != 0) { dp[i + 1][0] = min(dp[i + 1][0], dp[i][j] / a[i]); dp[i + 1][1] = max(dp[i + 1][1], dp[i][j] / a[i]); } } } cout << dp[n][1] << endl; return 0; }