30个免费货源网站,海淀网站开发公司,进出口贸易网站制作,站长工具无吗经典Leetcode 3584. Maximum Product of First and Last Elements of a Subsequence 1. 解题思路2. 代码实现 题目链接#xff1a;3584. Maximum Product of First and Last Elements of a Subsequence
1. 解题思路
这一题我们只需要从左往右依次遍历一下所有的元素#xff0c…Leetcode 3584. Maximum Product of First and Last Elements of a Subsequence 1. 解题思路2. 代码实现 题目链接3584. Maximum Product of First and Last Elements of a Subsequence
1. 解题思路
这一题我们只需要从左往右依次遍历一下所有的元素考察其作为子序列的起点位置 i i i时所能取到的最大值即可。显然要组成一个长为 m m m的序列那么其构成的子序列的最后一个元素位置至少为 i m − 1 im-1 im−1我们只需要考察从该位置开始的最大和最小元素即可。
因此我们只需要提前先计算出来每一个位置的右侧最大元素和最小元素即可。
唯一一个特殊情况是当 m 1 m1 m1时此时子序列有且仅有一个元素此时上述情况不成立但我们只需要找出原数组当中绝对值最大的元素即可答案即为其平方数。
2. 代码实现
给出python代码实现如下
class Solution:def maximumProduct(self, nums: List[int], m: int) - int:if m 1:return max([abs(x) for x in nums])**2n len(nums)right_min, right_max deepcopy(nums), deepcopy(nums)for i in range(n-2, -1, -1):right_min[i] min(nums[i], right_min[i1])right_max[i] max(nums[i], right_max[i1])ans -math.inffor i in range(n-m1):x nums[i]y1, y2 right_min[im-1], right_max[im-1]ans max(ans, x*y1, x*y2)return ans提交代码评测得到耗时812ms占用内存33.05MB。
