gpt4 book ai didi

arrays - 没有两个元素相邻的最大和

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:16:18 26 4
gpt4 key购买 nike

现在每个地方的可用解决方案是有一个 includeexclude 总和。最后这两个的 max 会给我输出。

最初我很难理解这个算法,我想为什么不以简单的方式进行。

算法:通过一次增加两个数组指针来遍历数组

  1. 计算数组中奇数位置的元素
  2. 计算偶数定位元素

最后,取这两个max

那样的话,我认为复杂度会降低一半O(n/2)

这个算法正确吗?

最佳答案

这是动态规划的一个例子。算法是:

  1. 不要采取(总结)任何非积极的项目
  2. 对于正数,将问题一分为二:尝试接受跳过该项目并返回这些选择中的最大值:

让我们展示第二步,假设我们得到:

[1, 2, 3, 4, 5, 6, 10, 125, -8, 9]

1 是正数,这就是为什么

take_sum = max(1 + max_sum([3, 4, 5, 6, 10, 125, -8, 9])) // we take "1"
skip_sum = max_sum([2, 3, 4, 5, 6, 10, 125, -8, 9]) // we skip "1"
max_sum = max(take_sum, skip_sum)

C#实现(最简单的代码,为了展示赤裸裸的思想,没有进一步优化):

private static int BestSum(int[] array, int index) {
if (index >= array.Length)
return 0;

if (array[index] <= 0)
return BestSum(array, index + 1);

int take = array[index] + BestSum(array, index + 2);
int skip = BestSum(array, index + 1);

return Math.Max(take, skip);
}

private static int BestSum(int[] array) {
return BestSum(array, 0);
}

测试:

Console.WriteLine(BestSum(new int[] { 1, -2, -3, 100 }));
Console.WriteLine(BestSum(new int[] { 100, 8, 10, 20, 7 }))

结果:

101        
120

请检查您的初始算法是否返回98117,它们是次优 总和。 p>

编辑:在现实生活中,您可能希望添加一些优化,例如内存和特殊情况测试:

private static Dictionary<int, int> s_Memo = new Dictionary<int, int>();

private static int BestSum(int[] array, int index) {
if (index >= array.Length)
return 0;

int result;

if (s_Memo.TryGetValue(index, out result)) // <- Memoization
return result;

if (array[index] <= 0)
return BestSum(array, index + 1);

// Always take, when the last item to choose or when followed by non-positive item
if (index >= array.Length - 1 || array[index + 1] <= 0) {
result = array[index] + BestSum(array, index + 2);
}
else {
int take = array[index] + BestSum(array, index + 2);
int skip = BestSum(array, index + 1);

result = Math.Max(take, skip);
}

s_Memo.Add(index, result); // <- Memoization

return result;
}

private static int BestSum(int[] array) {
s_Memo.Clear();

return BestSum(array, 0);
}

测试:

  using System.Linq;

...

Random gen = new Random(0); // 0 - random, by repeatable (to reproduce the same result)

int[] test = Enumerable
.Range(1, 10000)
.Select(i => gen.Next(100))
.ToArray();

int evenSum = test.Where((v, i) => i % 2 == 0).Sum();
int oddSum = test.Where((v, i) => i % 2 != 0).Sum();
int suboptimalSum = Math.Max(evenSum, oddSum); // <- Your initial algorithm
int result = BestSum(test);

Console.WriteLine(
$"odd: {oddSum} even: {evenSum} suboptimal: {suboptimalSum} actual: {result}");

结果:

  odd: 246117 even: 247137 suboptimal: 247137 actual: 290856

关于arrays - 没有两个元素相邻的最大和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47687173/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com