最大子数组差

题目链接: 45. 最大子数组差

给定一个整数数组,找出两个不重叠的子数组A和B,使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。

返回这个最大的差值。

Example:
给出数组 [1, 2, -3, 1], 返回 6 (|SUM([1,2]) - SUM([-3])|)

注意事项:子数组最少包含一个数

解题思路:

这题给人的第一感觉是可以用到最大子段和 Q53 Maximum Subarray。我们需要将数组划分为不重叠的两部分,求出左边最大子段和 leftMax,以及右边最小子段和 rightMin,然后相减求最大差值;或者求出左边最小子段和 leftMin 以及右边最大子段和 rightMax,然后相减求最大差值。

我们用4个 O(n) 的空间,利用最大字段和的动态规划的概念(最小子段和可以转化为最大字段和问题,只需要将列表中的元素全部取反,然后求最大字段和,再将结果取反即可。),分别存储 leftMax、rightMin、 leftMin、rightMax 这4个字段和,就可以在 O(n) 的时间内求出最大值

举例: nums = [2,-1,-2,1,-4,2,8]

  1. 从左到右,求左边的最大字段和 leftMax = [2, 1, -2, 1, -4, 2, 10]
  2. 从右向左,求右边的最小子段和 rightMin = [8, 2, -4, -3, -5, -6, -4] (之所以从右向左,是因为要保证两个子数组不重叠)
  3. 假设我们从 -2 的右边划分,则两个子数组为 [2,-1,-2] 和 [1,-4,2,8],分别对应的 leftMax 和 rightMin 为 [2, 1, -2] 和 [8, 2, -4, -3], leftMax 中应该是 2,rightMin 中应该是 -4,|2 - (-4)| = 6 。而 2 和 -4 对应的下标的关系为,将 rightMin 反转,-4 的下标比 leftMax 中 2 的下标多 1
  4. 因此,针对步骤 3 的方法,同时遍历求出的 leftMax 和 rightMin,即可找到左边最大子段和以及右边最小子段和,然后相减求最大差值
  5. 同理,将原数组反转,按照相同的方法,从左到右,求出的是右边的最大子段和 rightMax = [8, 10, 6, 7, 5, 4, 6] ;从右到左,求出的是左边的最小子段和 leftMin = [2, -1, -3, -2, -6, -4, 8],按照步骤 3 的方法,同时遍历求出的 rightMax 和 leftMin,即可找到右边最大子段和以及左边最小子段和,然后相减求最大差值
  6. 返回 步骤 4 和 步骤 5 中求得的两个最大差值的最大值,就是所求答案。
Python 实现:
class Solution:
    """
    @param nums: A list of integers
    @return: An integer indicate the value of maximum difference between two substrs
    """
    def maxDiffSubArrays(self, nums):
        if len(nums) <= 1: # 子数组最少包含一个数
            return 0
        return max(self.dealDiff(nums), self.dealDiff(nums[::-1]))

    # 最大子段和,返回子数组
    def maxSubArrays(self, nums):
        maxl = [nums[0]]
        for i in range(1, len(nums)):
            if maxl[i-1] < 0 or maxl[i-1] + nums[i] < 0:
                maxl.append(nums[i])
            else:
                maxl.append(maxl[i-1] + nums[i])
        return maxl 

    # 计算相减的结果,返回最大值
    def dealDiff(self, nums):
        retMax = float("-inf")  # 返回值
        leftMax = self.maxSubArrays(nums) # 从左到右,求最大子段和
        inverseNums = [-num for num in nums]
        # 最小子段和问题通过将各个元素取反可以转化为最大子段和问题
        inverseRightMin = self.maxSubArrays(inverseNums[::-1]) # 从右到左,求最小子段和
        rightMin = [-num for num in inverseRightMin][::-1]
        for i in range(1, len(leftMax)):
            retMax = max(retMax, abs(leftMax[i-1] - rightMin[i]))
        # print(leftMax, rightMin, retMax)
        return retMax

a = [2,-1,-2,1,-4,2,8]
print(Solution().maxDiffSubArrays(a)) # 16  # |[-1,-2,1,-4] - [2,8]|

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 最小方差划分

    给一个数组,求一个k值,使得前k个数的方差 + 后面n-k个数的方差最小 解题思路: 如果不考虑方差的概念,这题可以简化为 “给一个数组,求一个k值,使得前k个...

    echobingo
  • Q136 Single Number

    Given an array of integers, every element appears twice except for one. Find tha...

    echobingo
  • 【DP、Greedy】416. Partition Equal Subset Sum

    Given a non-empty array containing only positive integers, find if the array can...

    echobingo
  • VBA数组(一)基础知识

    大家好,前面介绍过VBA变量,可以通过它来访问数据。但对于大量数据时候,通过声明变量就显得太繁琐,此时就可以通过数组来访问数据解决。

    无言之月
  • 程序员算法面试中,必须掌握的数组理论知识

    数组是非常基础的数据结构,在面试中,考察数组的题目一般在思维上都不难,主要是考察对代码的掌控能力

    代码随想录
  • [Leetcode][双指针/多指针]相关题目汇总/分析/总结

    后端技术漫谈
  • Hey,Siri,帮我把服务器A的X目录凌晨五点拷贝到B服务器上

    人无法从海量的语料中学习到规律,但是语料经过数学化后,经历深度网络,网络的的节点通过某种群体行为能够记录下这种规律,从而在新的数据到来后,能够用这种隐藏的规律进...

    用户2936994
  • Flink集群部署

    上一节我们讲了单机模式如何部署启动,这节我们基于CentOS 7虚拟机搭建一个3个节点的集群:

    王知无
  • LeetCode 1296. 划分数组为连续数字的集合

    给你一个整数数组 nums 和一个正整数 k,请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。 如果可以,请返回 True;否则,返回 Fa...

    freesan44
  • 涨姿势 | 哈佛大学原创的开源软体机器人套件

    神马是软体机器人? 软体机器人是一个新兴机器人学领域。它是由生物学得到启发,利用柔性、可延展材料制成的结构结合而成的机器人。许多动植物都有柔性、弹性的身体结构,...

    机器人网

扫码关注云+社区

领取腾讯云代金券