0

我正在尝试编写一个最大子序列乘积程序，该程序基于最大子序列和程序的递归解决方案（也就是说，它将遵循相同的格式）。

到目前为止，它适用于所有情况，除了那些结果应该为“0”的情况，以表明序列中没有产品是正的。对于我下面的五个序列，它适用于除最后一个之外的所有序列：

sequence1 = new int[]{-2, 5, 4, 4};
sequence2 = new int[]{6, 5, 0, -3, -5, -3, 7};
sequence3 = new int[]{0, -1, 1, 5, 0, -3, -4};
sequence4 = new int[]{0, 3, 3};
sequence5 = new int[]{0, -3, 3};

这是递归方法，其中a是序列，p1最初是a[0]，p2是a[last index]：

public static int msp3(int[] a, int p1, int p2) {

    if (p1 == p2) {
        if (a[p1] != 0) {
            maxprod = a[p1];
        } else {
            maxprod = 0;
        }

    } else {
        int m = (p1 + p2) / 2;

        int L = msp3(a, p1, m);
        int R = msp3(a, m + 1, p2);

        int prodlt = 1, prodrt = 1, PL = 0, PR = 0;

        int checkForSplit = 0;

        for (int i = m; i >= p1; i--) {

            if (a[i] != 0) {
                prodlt = prodlt * a[i];

                if (prodlt > PL) {
                    PL = prodlt;
                }
            } else {
                if (i == m) {
                    prodlt = 1;
                    checkForSplit = 1;
                }
            }
        }

        for (int i = m + 1; i <= p2; i++) {
            if (a[i] != 0) {
                prodrt = prodrt * a[i];

                if (prodrt > PR) {
                    PR = prodrt;
                }
            } else {
                if (i == m + 1) {
                    prodrt = 1;
                    checkForSplit = 1;
                }
            }
        }

        if (checkForSplit == 0) {
            maxprod = max3(L, R, PL * PR);
        } else {
            maxprod = max3(L, R, PL);
            maxprod = max(maxprod, PR);
        }

    }
    return maxprod;
}

关于“checkForSplit”的注释，除非 a[i] == 0，否则该值为 0，并且我们正在检查当前子序列中最左边或最右边的索引，在这种情况下，它被设置为 1。这会触发不同的 ' max3' 其中 PL 不乘以 PR，逻辑是如果 PL 或 PR 为 0，则两者中的另一个可能不是，在这种情况下，它们不应相乘。

正如我所说，该算法适用于除第 5 个序列之外的所有序列。

有任何想法吗？

4

1 回答 1

0

空集的乘积是 1，而不是 0。所以如果你真的在做类似的问题，乘积永远不会低于 1。

因此，您实际尝试解决的问题更好地描述为“具有 2 个或更多成员的子序列的最大乘积”。为了解决这个问题，尝试提出一个递归函数，它接受序列和范围，并返回 4 个数字：

  1. 最小元素。
  2. 最大元素。
  3. 2个或更多元素的最小乘积。
  4. 2个或更多元素的最大乘积。

需要将 2 元素部分和 3 元素部分的情况编码为明显的特殊情况。

对于递归步骤，最小和最大元素的逻辑是显而易见的。最小和最大产品将是一侧的这 4 个数字之一与另一侧的这 4 个数字之一的 8 个可能产品中的最小值和最大值。

于 2014-09-23T12:48:52.053 回答