java - 选择两个大小相等的不相交子数组 A 和 B，使总和最大化 (A_1*B_k + A_2*B_(k-1) ... + A_k*B_1)，k = |A| = |乙|

Question

JLN 体育场举办了一场美食盛宴。来自不同州和城市的摊位已经摆好了。为了使节日更加有趣，还安排了多种游戏，人们可以玩这些游戏来赢取食品券。下面介绍其中一种赢取食品券的游戏:

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

如果参与者能够找到正确的最大总和，他/她将赢得比赛并获得相同值(value)的食品券。

注意:子序列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 个框的要求可能的最大总和。

Tamanna 也在狂欢中，想玩这个游戏。她需要帮助才能赢得比赛，并且正在寻求您的帮助。你能帮她赢得食品券吗？

输入格式

输入的第一行由框数 N 组成。

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

约束

1< N <=3000

-10^6 <=我<=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

这是一个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 是有效选择的第一个，然后是第二个，然后是第三个，依此类推。在每次迭代中，我们将递增 i 并递减 j，这样我们就沿对角线移动:6, 10, -12，每次添加倍数以扩展我们的选择范围。

我们可以在每个对角线上执行此操作以获得从 (i, j) 开始的最佳选择，其中 i 是第一个，然后是第二个，然后是第三个，等等

现在假设我们运行了 Kadane's algorithm在从东北到西南的每条对角线上(直到 x 所在的位置 i = j)。复杂度 O(n^2) 时间。 (revisions 中有 Python 代码。)