如何获得二维数组的前缀最大和

Question

我有一个二维数组，大小为n*k。我必须从矩阵中选择p项，以便仅从每行中选择前缀，以使权重最大化。

例如：n = 2, k = 4, p = 5

数组是：

10 10 100 30

80 50 10 50

最大总和就像从第一行中选择3个元素，从第二行中选择2个元素，使总和为250。

约束为n <= 50，k <= 30和p <= n * k。数组中的元素范围可以从1到100。

Answer 1

这是一个简单的问题，里面没有类似背包的概念。您只需要使用for循环即可。

1. 选择array1的p个元素并找到其总和。在您的示例中，完全选择array1，然后选择array2的其余元素。添加的元素：[10,10,100,30,80]sum = 230
2. 然后一个接一个地从后面和后面删除array1的元素array2开始将元素逐一加和并计算最大金额，这将是您的答案。
   1. 从总和中删除array1的最后一个元素（30），然后将array2的下一个元素相加（50）。元素是添加：[10,10,100,80,50] sum = 250
   2. 从总和中删除array1的倒数第二个元素（即100），然后将array2的倒数第二个元素（即10）相加。元素是添加：[10,10,80,50,10] sum = 160
   3. 从总和中删除array1的最后一个元素（10），然后将array2的下一个元素相加（50）。元素是添加：[10,80,50,10,50] sum = 200

当没有元素要从array1删除到总和时，或者没有元素要从array2添加到总和时，您必须停止。因此，所需的答案将是所有计算出的总和中的最大总和。