# 合并箱子重量 —— 亚马逊 2022 面试题

#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;

# 代码
```csharp
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)]`