仅当乘积小于等于 k

Question

我最近在一次在线评估中遇到了这个问题。

arr = [2,6,2,4] 
k = 15

数组元素需要通过仅将两个相邻元素相乘并且仅当它们的乘积小于

k

.

例子：

(2,6,2,4)
(2*6,2*4) --> since 12 and 8 are less than k which is 15
(12,8)

也可以遵循以下模式：

(2,6,2,4)
(2,6*2,4) 
(2,12,4) --> no . of  elements is 3 which is more than 2 thus non-optimal.

我已经被这个问题困了好几天了

我尝试通过 Matrix Chain Multiplication 问题解决它，但我无法取得任何进展。主要区别在于，在 MCM 问题中，所有矩阵都可以相互相乘。不存在 2 个矩阵不能相乘的情况。

任何提示？

Answer 1

由于数组的值严格为正，您可以使用贪心算法：不断乘以值，直到下一次乘法为

k

或更多。发生这种情况时，启动一个新块并将乘积重置为当前数组值。通过这种方式，我们将块边界尽可能地放在右边。我们可以看到，如果我们将一个块边界向左移动更多，这将永远不会减少所需的块数。

这里是这个贪心算法在（简单的）JavaScript 中的一个实现：

function solve(arr, k) {
    if (arr.length == 0) return 0; // Boundary case
    
    let product = 1;
    let count = 1;
    
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] >= k) return arr.length; // Boundary case
        product = product * arr[i];
        if (product >= k) { // Start a new chunk
            product = arr[i];
            count++;
        }
    }
    return count;
}

// Example run
const arr = [2,6,2,4]; 
const k = 15;
const result = solve(arr, k);
console.log("Number of chunks", result);

如果我们允许 0 作为可能的数组值，并且

k

严格为正，则零的出现将导致结果 1：所有值都可以乘以一个乘积 0.

如果允许负数组值，该算法将不再正确工作。