#leetcode #算法

题目

Consider n packages, where packageWeights[i] represents the weight of the i th package, You can combine i th and i+1 th package if packageWeights[i] <packageWeights[i+1] and then discard the i th package. After this operation number of packages reduces by 1 and weight of i+1 th package increases by packageWeights[i]. You can merge as many times as you want. Find the max possible weight of the package that can be achieved after any sequence of merge operations

Eg packageWeights =[2,9,10,3, 7] optimal order:

• iteration 1 combine packages at index 2 and 3 ->new packageWeights =[2,19,3,7]
• iteration 2 combine packages at index 1 and 2 ->new packageWeights =[21,3,7]
• iteration 3 combine packages at index 2 and 3 ->new packageWeights =[21,10]
• No more packages can be combined. The weight of the heaviest package is 21 Result:21

分析

其实例子中给出来的分析已经足够。在理解这个问题的时候，可以直接尝试着用程序化的语言来理解，比如：

1. packageWeights =[2,9,10,3, 7]; var max = 0;
2. var index = 4; value = 7; current = 7; max = 7;
3. index = 3; value = 3; value < current; current = 7 + 3; max = 10;
4. index = 2; value = 10; value !< current; current = value(10); max = 10;
5. index = 1; value = 9; value < current; current = 10 + 9; max = 19;
6. index = 0; value = 2; value < current; current = 19 + 2; max = 21;
7. return max;

代码

var packageCount = packageWeights.Length;
var max = 0;
if (packageCount == 0) { return max; }

var current = packageWeights[^1];
for (int index = packageCount - 1; index >= 0; index--)
{
    var value = packageWeights[index];
    current = value < current
        ? current + value
        : value;
    max = Math.Max(max, current);
}

return max;

有没有发现，在上一步中，当你用程序化的思维去理解这个问题的时候，编程就成了一种自然而然的语言转换了。 时间复杂度：O(n) 空间复杂度：O(1)

测试案例

如果你是在面对面的跟面试官沟通的话，往往面试官会问你要怎么设计测试用例。 其实这个也是考察你对编码的严谨性的。

本题的测试案例可以这样逐步来想：

1. 只有一条重量数据：[TestCase(new[] { 2 }, ExpectedResult = 2)]
   1. 增加一个大重量的包在前面：[TestCase(new[] { 10, 2 }, ExpectedResult = 10)]
      1. 增加一个相同重量的包在前面：[TestCase(new[] { 10, 10, 2 }, ExpectedResult = 10)]
      2. 增加一个相同重量的包在后面：[TestCase(new[] { 10, 2, 2 }, ExpectedResult = 10)]
   2. 增加一个大重量的包在后面：[TestCase(new[] { 2, 10 }, ExpectedResult = 12)]
2. 合并之后有两个包：[TestCase(new[] { 2, 9, 10, 3, 7 }, ExpectedResult = 21)]
3. 合并之后只有一个包：[TestCase(new[] { 2, 9, 10, 3, 8 }, ExpectedResult = 32)]