最大乘积和，本题是2022年4月17日举办的第13届蓝桥杯青少组Python编程省赛真题编程部分第5题，13届一共举办了两次省赛，这是第一次省赛。题目要求对于N个正整数，编程计算出所有乘积相加的数值最大的排列方式，并输出数值。
先来看看题目的要求吧。
编程实现：
有N个正整数，现对N个正整数进行不同方式的排列，每次排列后都会按照以下规则进行一次计算，聪明的小蓝发现，排列方式不同，最后计算出的结果也不相同。
计算规则：
第一次：第一个数乘以第二个数乘以第三个数，结果记录为M(1) ；
第二次：第二个数乘以第三个数乘以第四个数，结果记录为M(2) ;
第三次：第三个数乘以第四个数乘以第五个数，结果记录为M(3) ;
…
第N − 2次：第N − 2个数乘以第N − 1个数乘以第N个数，结果记录为M ( N − 2 ) 。
最后计算M(1) + M(2) + M(3) . . … . M(N − 2)的数值。找出一种排列方式使这个数值最大。
例如：N = 4，4个正整数分别为1，2，3，4，那么排列方式就会有24种，其中排列方式为1，3，4，2时，按照规则计算2次：1 × 3 × 4 = 12，3 × 4 x 2 = 24，乘积相加：12 + 24 = 36 这种排序方式是所有乘积相加的数值最大，为36。
输入描述：
输入N个正整数，正整教之间一个英文逗号隔开。
输出描述：
找出所有乘积相加的数值最大的排列方式，并输出数值。
输入样例：
1,2,3,4
输出样例：
这是一道和排列组合相关的算法题，涉及的知识点包括循环、列表、排列函数、枚举算法和贪心算法等。
枚举算法 + 排列函数 贪心算法
M(1) = a * b * cM(2) = b * c * dM(3) = c * d * e
两端的a和e，都只参与了一次运算； 左2的b和右2的d，参与了两次运算； 中间位置的c，参与了3次运算；
如果有6个数字，分别是2、3、5、7、8、10，最大的两个数8和10要放在中间，紧接着7和10挨着，5则和8挨着，3和2分列两端，如图：
将列表进行排序 分别获取奇数位的数字和获取偶数位的数字 奇数位数字正序，偶数位数字逆序，构成一个新列表 分别计算M(1)、M(2)、...、M(n- 2)，并求和
枚举算法 + 排列函数
贪心算法
1. 枚举算法 + 排列函数
根据前面的思路分析，编写代码如下：
代码不多，说明3点：
1). 对n个数字获取全排列，第一个参数为列表，第二个参数是n；
2). permutations()函数得到的是可迭代对象，使用for循环来获取每一个对象，该对象是元组；
3). 在获取最大值的时候，直接使用了max()函数。
2. 贪心算法
根据前面的思路分析，编写代码如下：
代码不多，强调3点：
1). 在获取奇数和偶数列表的时候，使用了带条件的列表推导式，非常方便；
2). 列表逆序，直接使用切片运算[::-1]，方便快捷；
3). 在Python编程中，可以直接将两个列表相加，得到新的列表。
循环语句；
列表推导式；
排列函数；
枚举算法；
贪心算法；
本题代码不算多，但是难度不小，关键点有两个，一是灵活运用Python自带的排列函数快速解决问题，二是分析乘法算式的特点，找到数字排列的规律，从而找到更高效的算法。
本题给出了两个解决方案，方案一相对比较简单，但并不是最优的方案，大概率会出现超时情况，因为它的时间复杂度太高了。
permutations()函数的时间复杂度取决于输入的数据大小，对于包含n个元素的列表，它会生成n的阶乘个排列，因此，其时间复杂度可以表示为O(n!)。
当n值很大时，阶乘的增长非常快，导致permutations()函数的性能会随着输入大小的增加而急剧下降。
你可以输入1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13，来测试一下方法一的效果。
因此，在数据较多的时候，必须要考虑使用其他更高效的方法来避免计算所有排列。
而方案二则使用了贪心算法的思想，找出数字排列的规律，最后通过一次循环就可以计算出最大乘积和。
由于使用了排序函数，因此其时间复杂度主要取决于sort()函数。在Python编程中，sort()方法使用的是Timsort算法，其时间复杂度为O(n log n)，其中n是列表的长度。
Timsort算法由Tim Peters在2002年为Python编程语言提出的，并已成为Python sort()方法和sorted()函数的默认排序算法。
Timsort算法是一种混合了归并排序和插入排序思想的排序算法，针对不同情况下的数据集均具有较好的性能表现。
你还有什么好的想法和创意吗，也非常欢迎和超平老师分享探讨。
需要源码的，可以添加本人微信。
另外，超平老师创建了一个蓝桥杯备考交流群，这是专门为老师和家长打造的免费社群，您可以与来自全国各地的老师、家长共同交流经验，分享学习心得。
超平老师也会给大家带来及时的赛事动态，备考攻略，真题资源分享，帮助各位更好地备考第15届蓝桥杯赛事，力争取得优异的成绩。
扫码或长按加入微信群
