动态编程查找数组中元素的乘积和和的最大值

Question

嗨，我有以下问题，我想实现：

给定整数数组：1 2 7 5 1 2 我想找到最大相邻乘积之和，即1+2+(5*7)+1+2 = 41

给定整数数组：1 2 4 2 4 2我想找到最大相邻乘积之和 1+(2*4)+(2*4)+2 = 19

乘法的约束是只能将一个相邻元素用于乘法。也就是说，如果我们有2 4 2数组，我们将其计算为2+(4*2) or (2*4)+2。

我是动态编程的初学者。我无法弄清楚以下问题的重复关系。

有人可以建议点什么吗？

Answer 1

逐步解决方案是这样的：

• 考虑第一个元素，没有其他元素时最大。
• 当您的所有元素都没有出现时继续。
• 添加第i个元素：
  • F（i）=最大{F（i-1）+ e _i，f（i-2）+ e _i-1 * e _i）

其中F（i）是您的第i个元素的最大值，而e _i是您的第i个元素。

考虑一下： 1 2 4 3 4

• 首先我们有F(1) = 1。
• 然后F(2) = 1 + 2。
• 然后我们比较F(2) + 4 = 1 + 2 + 4，F(1) + 2 * 4= 1 + 2 * 4事实就是如此F(3) = 1+2*4 = 9。
• 那么你有F(2) + 4 * 3 = 1 + 2 + 4 * 3和F(3) + 3 = 1 + 2 * 4 + 3故F(4) = 1 + 2+ 4*3 = 15
• 那么你有F(4) + 4 = 1 + 2 + 4 * 3 + 4和F(3) + 3*4 = 1 + 2 * 4 + 3 * 4故F(5) = 1 + 2 * 4 + 3 * 4 = 21