B. Maximum Product
time limit per test2 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
You are given an array of integers ??1,??2,…,????. Find the maximum possible value of ???????????????????? among all five indices (??,??,??,??,??) (??<??<??<??<??).

Input

The input consists of multiple test cases. The first line contains an integer ?? (1≤??≤2?104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer ?? (5≤??≤105) — the size of the array.

The second line of each test case contains ?? integers ??1,??2,…,???? (?3×103≤????≤3×103) — given array.

It‘s guaranteed that the sum of ?? over all test cases does not exceed 2?105.

Output

For each test case, print one integer — the answer to the problem.

Example

input

4
5
-1 -2 -3 -4 -5
6
-1 -2 -3 1 2 -1
6
-1 0 0 0 -1 -1
6
-9 -7 -5 -3 -2 1

output

-120
12
0
945

Note

In the first test case, choosing ??1,??2,??3,??4,??5 is a best choice: (?1)?(?2)?(?3)?(?4)?(?5)=?120.

In the second test case, choosing ??1,??2,??3,??5,??6 is a best choice: (?1)?(?2)?(?3)?2?(?1)=12.

In the third test case, choosing ??1,??2,??3,??4,??5 is a best choice: (?1)?0?0?0?(?1)=0.

In the fourth test case, choosing ??1,??2,??3,??4,??6 is a best choice: (?9)?(?7)?(?5)?(?3)?1=945.

题意

给你一个序列，让你选五个数乘积最大

解决

01背包，同时维护最大值最小值，因为有负数，所以可能负负得正

#include <bits/stdc++.h>

#define INF 243000000000000001
#define MAXN 123456
#define LL long long

using namespace std;

int t;
int n;
LL a[MAXN];
LL maxn[6];
LL minn[6];

inline void init() {
  maxn[0] = 1;
  minn[0] = 1;
  for (int i = 1; i < 6; i++) {
    maxn[i] = -INF;
    minn[i] = INF;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> t;
  while (t--) {
    init();
    cin >> n;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
      for (int j = min(i + 1, 5); j >= 1; j--) {
        maxn[j] = max(maxn[j], max(maxn[j - 1] * a[i], minn[j - 1] * a[i]));
        minn[j] = min(minn[j], min(maxn[j - 1] * a[i], minn[j - 1] * a[i]));
      }
    }
    cout << maxn[5] << "\n";
  }
  return 0;
}

Codeforces Round #670 (Div. 2) B. Maximum Product

原文：https://www.cnblogs.com/wuwangchuxin0924/p/13659455.html