目錄

• 1. 最大子序和（變體）
• 2. 矩陣求乘積最大
• 3. 逐漸平均——值最大

目前已更新：第一題，第二題，第四題

1. 最大子序和（變體）

題目描述：

首先考慮常規的最大子序和的問題，即不能去掉中間的一段，leetcode上有一個這樣 的題目：

leetcode——最大子序和題解

分析如下：

考慮數組中某一位置的元素nums[i]，如果nums[i] + (i 前面若干個連續數組成的累計和) > nums[i] ，則表示加上nums[i] 之后會組成更大的子序和，我們就把相加值賦給nums[i] ，反之，則不動nums[i]的值，這之后的nums[i]表示：從前往后遍歷，到i 這個位置時的最大子序和（注意：nums[i] 必須在包含里面，表示包含nums[i]的最大子序和，而不是nums[:i+1]的最大子序和）。參考下圖：

而我們這個問題有個附加條件：可以去掉中間的一段。

假如我們隨便去掉中間的一段，則數組被分成兩段（數組1，數組2）：

最大子序和 = 數組1從前往后遍歷的最大子序和 + 數組2從后往前遍歷的最大子序和

這里有一個問題就是如果數組1最大子序和不是出現在數組1最后的位置，還等價嗎？其實是等價的，相當于多去掉一段，并不影響結果。因此，代碼可以寫成：

class Solution:def maxSubArray(self, nums: List[int]) -> int:nums = [0] + nums # 加一個0是為了防止全負數的情況,這種情況下則不包含任何元素，子序和為0nums1 = nums[:]nums1.reverse() # 復制一份，并反轉數組n = len(nums)for i in range(1,n):nums[i] = max(nums[i],nums[i-1]+nums[i]) # 從前往后的最大子序和nums1[i] = max(nums1[i],nums1[i-1]+nums1[i]) # 從后往前的最大子序和# 遍歷數組，找最大值max_ = 0for i in range(n-1):for j in range(0, n-i-1):max_ = max(max_, nums[i]+nums1[j])print(nums,nums1)return max_

2. 矩陣求乘積最大

題目描述：

這一題可以簡化，以其中的兩行為例：

• 若第一行的最大值的序號與第二行的最大值的序號互異，則這兩行乘積的最大值為兩行分別的最大值相乘；

• 若第一行的最大值得序號與第二行的最大值的序號相等，說明某一行的最大值的序號與另一行的第二大值得序號必互異，則乘積最大值在某一行的最大值與另一行的第二大的值的乘積當中（共有兩個，取最大的）

代碼如下：

nums = [[1,2,3,4], [5,6,7,8], [9,10,11,12]] n = len(nums) m = len(nums[0]) target = []for i in range(n):tmp = [[-float("inf"), -1], [-float("inf"), -1]] # 存儲當前行的最大值，第二大的值以及他們各自的序號for j in range(m):if nums[i][j] > tmp[0][0]:tmp[1] = tmp[0][:]tmp[0][0] = nums[i][j]tmp[0][1] = jtarget.append(tmp)max_ = -float("inf") for i in range(n):for j in range(i+1,n):if target[i][0][1] != target[j][0][1]: # 如果最大值兩個序號不相等，則這兩行的最大值是兩行各自最大值的乘積max_ = max(target[i][0][0]*target[j][0][0], max_)else: # 反之則說明這兩行中某一行的最大值的序號和另一行的第二大的值的序號是互異的max_ = max(target[i][0][0]*target[j][1][0], target[i][1][0]*target[j][0][0], max_)print(max_)

3. 逐漸平均——值最大

題目描述：

這題思路很簡單：

• 首先要明確一點，最先加入的數被除的次數最多，比如第一個數，他就相當于除以了2^(n-1)，每次除，這個數都會減少一半。基于這個思想，我們要做到的是，要讓最大的數盡量少被除，因此我們可以先排序，然后一遍遍歷就可以解決。

代碼如下：

nums = [4,5,2,6,1,7,5,9]nums.sort() target = round(nums[0],4) for i in range(1,len(nums)):target = round((target + nums[i])/2, 4)print(target)

轉載于:https://www.cnblogs.com/anzhengyu/p/11228550.html

總結

以上是生活随笔為你收集整理的2019招商银行M-Geeker线上比赛题解析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。