最大K个子数组和

Question

最大K个子数组和

algorithmsumdynamic-programmingmaxarrays

3

我在处理这个问题时遇到了记忆化和自底向上的算法困难：

假设你有一个元素数组xi，满足对于所有0 < i < N，-10000 < xi < 10000。尝试找到T个元素（T < N），使它们排列在不同的子数组中，以获得最大总和。我们不会将每个子数组的第一个元素相加，并且还必须返回子数组的数量K。

例如：

当T = 4, 数组为3 9 1 1 7 => (3 9)和(1 7)具有最大和16 = 9 + 7，K = 2

当T = 4, 数组为3 9 6 3 7 => (3 9 6 3)具有最大和18 = 9 + 6 + 3，K = 1

当T = 9, 数组为14 11 18 1 1 16 12 18 0 0 11 18 9 5 14 => 连续子数组为(14 11 18)(1 16 12 18)(11 18)，K = 3，max_sum = 11 + 18 + 16 + 12 + 18 + 18 = 93

当T = 15, 数组为6 19 -29 15 9 -4 5 27 3 12 -10 5 -2 27 10 -2 11 23 -4 5 => 连续子数组为(6 19) (-29 15 9) (5 27 3 12) (-2 27 10) (-2 11 23)，K = 5，max_sum = 19 + 15 + 9 + 27 + 3 + 12 +27 + 10 + 11 + 23 = 156。

我到目前为止做的是：

令f[i][j][0]表示使用j个插槽时前i个插槽的最大和，第i个插槽未使用。

令f[i][j][1]表示使用j个插槽时前i个插槽的最大收益，第i个插槽已使用。

显然，f[i][j][k]可以确定f[i+1][j][k]或f[i+1][j+1][k]

详细信息：

    f[i+1][j+1][1]=max(f[i+1][j+1][1],f[i][j][0],f[i][j][1]+G[i+1]);
    f[i+1][j][0]=max(f[i+1][j][0],f[i][j][0],f[i][j][1]);

- Mougart

示例不清楚：为什么不是 T=4, array = 3 9 1 1 7 => (3 9 1 1 7) 具有最大和18 = 9 + 1 + 1 + 7，K = 1？ - anatolyg

抱歉我之前没有提到，我们需要在不同的子数组中挑选T个元素，使它们的和最大，并且每个子数组的第一个元素不能与其他元素相加。所以在例子中 T=4, array = 3 9 1 1 7 中，我们需要挑选4个元素，最佳方案是 **(3 9) 和 (1 7)**，因为7 + 9 = 16，而每个子数组的第一个元素（3和1）并不重要。在任何其他情况下，我们得到的总和都会更小。希望这样更清楚明白了 :) - Mougart

也许使用“连续子序列/子列表”或者至少是“连续子数组”会更为恰当？例如，3、9、1、7也是3、9、1、1、7的一个“子数组”，其和为17。可能需要添加一些例子，因为这个问题有点难以理解。 - fsw

我将添加更多的例子：**T = 9，数组=14 11 18 1 1 16 12 18 0 0 11 18 9 5 14 => 连续的子数组为(14 11 18) (1 16 12 18) (11 18)，K = 3，max_sum = 11 + 18 + 16 + 12 + 18 + 18 = 93 ** **对于T = 15，数组=6 19 -29 15 9 -4 5 27 3 12 -10 5 -2 27 10 -2 11 23 -4 5 => 连续的子数组为(6 19) (-29 15 9) (5 27 3 12) (-2 27 10) (-2 11 23)，K = 5，max_sum = 19 + 15 + 9 + 27 + 3 + 12 + 27 + 10 + 11 + 23 = 156。 - Mougart

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- גלעד ברקן · Answer 1

这是Haskell版本的代码。函数“partitions”由Daniel Fischer编写，它将列表（或数组）分成所有可能的方式。代码的其余部分测试长度大于一且组合长度等于T的元素的分区，并返回总和最大的那个（按要求不包括第一个数字进行求和）。

import Data.List (maximumBy)
import Data.Ord (comparing)

partitions [] = [[]]
partitions (x:xs) = [[x]:p | p <- partitions xs]
                 ++ [(x:ys):yss | (ys:yss) <- partitions xs]

findMax t xs = 
  let toTest = filter (\z -> (sum $ map length z) == t) 
               $ map (\x -> filter (\y -> length y > 1) x) 
               $ partitions xs
      result = maximumBy (comparing snd) 
               (zip toTest (map (\x -> sum $ map (sum . drop 1) x) toTest))
  in putStrLn( 
       show result 
       ++ " K = " 
       ++ show (length $ fst result))


OUTPUT:
*Main> findMax 4 [3,9,1,1,7]
([[3,9],[1,7]],16) K = 2

*Main> findMax 4 [3,9,6,3,7]
([[3,9,6,3]],18) K = 1

*Main> findMax 9 [14,11,18,1,1,16,12,18,0,0,11,18,9,5,14]
([[14,11,18],[1,16,12,18],[11,18]],93) K = 3