选择两个大小相等的不相交子数组A和B，使总和最大化（A_1*B_k A_2*B_（k-1）…A_k*B_1），k=|A|=|B|

Question

JLN体育场组织了一场美食节。来自不同州和城市的摊位已经摆好。为了让节日更加有趣，安排了多个游戏，人们可以玩这些游戏来赢得食物券。下面描述了一个赢得食品券的游戏：

有N个盒子排列在一个队列中。每个盒子上都有我写的一个整数。从给定的队列中，参与者必须选择两个相同大小的连续子序列A和B。所选择的子序列应该是这样的，即盒子的乘积之和应该是最大的。虽然乘积不是正常计算的。为了使游戏有趣，子序列A的第一个盒子要乘以子序列B的最后一个盒子，子序列A的第二个盒子要乘以子序列B的倒数第二个盒子，依此类推。然后将如此获得的所有产物加在一起。

如果参与者能够找到正确的最大总和，他/她将赢得游戏，并将获得同等价值的食物券。

注意:子序列A和B应该是不相交的。

例：

盒子数量，N = 8

盒子的顺序如下：

1 9 2 3 0 6 7 8

子序列A

9 2 3

子序列B

6 7 8

子序列的乘积将计算如下:

P1=9*8=72

P2 = 2 * 7 = 14

P3 = 3 * 6 = 18

求和，S=P1 P2 P3=72 14 18=104

这是根据给定 N 个框的要求可能的最大总和。

塔曼娜也在节日中，想玩这个游戏。她需要帮助才能赢得比赛，并正在寻求你的帮助。你能帮她赢得食物券吗？

输入格式

输入的第一行包括盒子的数量n。

输入的第二行由 N 个空格分隔的整数组成。

制约因素

一

-10^6

输出格式在单独的行中打印方框乘积的最大总和。

示例测试用例 1 输入

8
1 9 2 3 0 6 7 8

输出

104

我的代码是这个，它只通过了一个测试，任何人都可以告诉我出了什么问题，我没有其他测试用例，因为它们隐藏了

import java.util.Scanner;
import java.util.*;

public class Main {
    
    static class pair {
        int first, second;
        
        public pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
    
    static int getSubarraySum(int sum[], int i, int j) {
        if (i == 0)
            return sum[j];
        else
            return (sum[j] - sum[i - 1]);
    }
    
    static int maximumSumTwoNonOverlappingSubarray(int arr[], int N,
            int K) {
        int l = 0, m = 0;
        int a1[] = new int[N / 2];
        int a2[] = new int[N / 2];
        int prod = 0;
        int[] sum = new int[N];
        sum[0] = arr[0];
        
        for (int i = 1; i < N; i++)
            sum[i] = sum[i - 1] + arr[i];
        
        pair resIndex = new pair(N - 2 * K, N - K);
        
        int maxSum2Subarray =
                getSubarraySum(sum, N - 2 * K, N - K - 1)
                        + getSubarraySum(sum, N - K, N - 1);
        
        pair secondSubarrayMax =
                new pair(N - K, getSubarraySum(sum, N - K, N - 1));
        
        for (int i = N - 2 * K - 1; i >= 0; i--) {
            int cur = getSubarraySum(sum, i + K, i + 2 * K - 1);
            if (cur >= secondSubarrayMax.second)
                secondSubarrayMax = new pair(i + K, cur);
            cur = getSubarraySum(sum, i, i + K - 1)
                    + secondSubarrayMax.second;
            if (cur >= maxSum2Subarray) {
                maxSum2Subarray = cur;
                resIndex = new pair(i, secondSubarrayMax.first);
            }
        }
        
        for (int i = resIndex.first; i < resIndex.first + K; i++) {
            a1[l] = arr[i];
            l++;
        }
        
        for (int i = resIndex.second; i < resIndex.second + K; i++) {
            a2[m] = arr[i];
            m++;
        }
        
        for (int i = 0; i < m; i++) {
            if (a1[i] != 0 || a2[i] != 0) {
                prod = prod + a1[i] * a2[m - (i + 1)];
            }
        }
        return prod;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int k = 0;
        int arr[] = new int[a];
        
        for (int i = 0; i < a; i++) {
            arr[i] = sc.nextInt();
        }
        
        int l = arr.length;
        int ar[] = new int[a / 2];
        
        for (int i = 1; i <= a / 2; i++) {
            ar[k] = maximumSumTwoNonOverlappingSubarray(arr, l, i);
            k++;
        }
        
        Arrays.sort(ar);
        System.out.println(ar[k - 1]);
    }
}

Answer 1

    
#include <iostream>

#include <cassert>

using namespace std;

template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }

template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }

template<class T> inline T abs(T a){return a>0 ? a : -a;}

template<class T> inline T gcd(T a,T b){return __gcd(a, b);}

template<class T> inline T lcm(T a,T b){return a/gcd(a,b)*b;}

typedef long long ll;

typedef pair<int, int> ii;

const int inf = 1e9 + 143;

const ll longinf = 1e18 + 143;

inline int read()

{

int x;scanf(" %d",&x);

return x;

}

const int N = 20001;

int n;

int a[N];

void read_inp()

{

   n = read();

   assert(1 <= n && n <= 20000);

   for(int i = 1; i <= n; i++)

{

       a[i] = read();

       assert(abs(a[i]) <= int(1e6));

   }

}

int main()

{

#ifdef KAZAR

   freopen("f.input","r",stdin);

   freopen("f.output","w",stdout);

   freopen("error","w",stderr);

#endif

   read_inp();

   ll ans = -longinf;

   for(int i = 1; i <= n; i++)

{

       {

           int l = i - 1, r = i;

           ll best = 0ll, cur = 0ll;

           while(l >= 1 && r <= n)

  {

               ll val = (ll)a[l] * a[r];

               cur += val;

               umin(best, cur);

               umax(ans, cur - best);

               --l;

               ++r;

           }

       }

 {

           int l = i - 1, r = i + 1;

           ll best = 0ll, cur = 0ll;

           while(l >= 1 && r <= n)

  {

               ll val = (ll)a[l] * a[r];

               cur += val;

               umin(best, cur);

               umax(ans, cur - best);

               --l;

               ++r;

           }

       }

   }

   printf("%lld\n",ans);

   return 0;

}

Answer 2

这是密码

n=int(input())
l=[]
res=0
l=list(map(int,input().split()))
re=[]
while(True):
    if(len(l)==2):
        pass
        break
    else:
        n1=l[1]
        n2=l[-1]
        re.append(n1*n2)
        l.remove(n1)
        l.remove(n2)
for i in re:
    res=res+i
print(res)

Answer 3

这是一个O（n^2）时间，O（1）空间解。

让我们将所有 O（n^2） 倍数写入矩阵中。例如：

Input {1, 2, 3, -4, 5, 6}

    1   2   3  -4   5   6
 1  x   2   3  -4   5   6
 2      x   6  -8  10  12
 3          x -12  15  18
-4              x -20 -24
 5                  x  30
 6                      x

现在选择任何索引（i， j），i≠j，说（0,5）。

                          j
      1   2   3  -4   5   6
i  1  x   2   3  -4   5   6
   2      x   6  -8  10  12
   3          x -12  15  18
  -4              x -20 -24
   5                  x  30
   6                      x

现在想象一下，我们想要找到一个有效的选择的最佳子数组，在那里我是第一个，然后是第二个，然后是第三个，依此类推。在每次迭代中，我们将递增 i 并递减 j，这样我们就在对角线上移动：6， 10， -12，每次添加倍数以扩展我们的选择。

我们可以在每条对角线上这样做，以从< code>(i，j)开始获得最佳选择，其中< code>i是第一个，然后是第二个，然后是第三个，依此类推。

现在想象一下，我们在从东北到西南的每个对角线上运行Kadane算法（直到xs在哪里，i = j）。复杂度 O（n^2） 时间。（其中一个修订版中有 Python 代码。