1749. 任意子数组和的绝对值的最大值

这篇具有很好参考价值的文章主要介绍了1749. 任意子数组和的绝对值的最大值。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

诸神缄默不语-个人CSDN博文目录
力扣刷题笔记

1749. 任意子数组和的绝对值的最大值,编程学习笔记,力扣,LeetCode,算法,算法与数据结构

1749. 任意子数组和的绝对值的最大值,编程学习笔记,力扣,LeetCode,算法,算法与数据结构

1. 暴力搜索

直接用2个指针从索引0开始找到最后一个索引,时间复杂度大概是 O ( n 2 ) O(n^2) O(n2)吧,总之这么搞不行,以下是我用Python写的一些典型失败案例

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        max_abs=0
        nums_len=len(nums)
        for pointer1 in range(nums_len):
            for pointer2 in range(pointer1,nums_len):
                sub_nums=nums[pointer1:pointer2+1]
                max_abs=max(max_abs,abs(sum(sub_nums)))
        return max_abs

↑会超时,这个我觉得应该是sum()的问题,所以做了改进:

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        sum_table=[[0 for _ in range(len(nums))] for _ in range(len(nums))]
        for i in range(len(nums)):
            sum_table[i][i]=nums[i]
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                sum_table[i][j]=sum_table[i][j-1]+nums[j]
        max_abs=0
        for i in sum_table:
            for j in i:
                max_abs=max(max_abs,abs(j))
        return max_abs

↑这个又会爆内存,我骂骂咧咧。
这个我一开始猜是因为0太多了,所以把所有一直都是0的部分给删除了:

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        sum_table=[[0 for _ in range(len(nums)-i)] for i in range(len(nums))]
        for i in range(len(nums)):
            sum_table[i][0]=nums[i]
        for i in range(len(nums)):
            for j in range(1,len(nums)-i):
                sum_table[i][j]=sum_table[i][j-1]+nums[j+i]
        max_abs=0
        for i in sum_table:
            for j in i:
                max_abs=max(max_abs,abs(j))
        return max_abs

↑还是会爆内存
继续缩:

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        max_abs=0
        for i in range(len(nums)):
            pre_sum=nums[i]
            max_abs=max(max_abs,abs(pre_sum))
            for j in range(i+1,len(nums)):
                pre_sum=pre_sum+nums[j]
                max_abs=max(max_abs,abs(pre_sum))
        return max_abs

这回超时了

2. 动态规划

然后我就去看题解了。

来自官方题解:https://leetcode.cn/problems/maximum-absolute-sum-of-any-subarray/solutions/2372374/ren-yi-zi-shu-zu-he-de-jue-dui-zhi-de-zu-qerr/

在一组数字中绝对值的最大值,可能是最大的值的绝对值,也可能是最小值的绝对值。
所以找子数组和绝对值的最大值,就要找最大的子数组和,和最小的子数组和。
所以解决方案是分别计算这两种情况:在找最大的子数组和时,遍历数组,保留到上一个数字为止的全局子数组最大和global_max+有上一个数字在的子数组的最大和sumable_max或者0(0的意思就是甩掉上一个数字),如果新数字+sumable_max比positiveMax还高,就更新global_max;如果这个数字加进sumable_max大于0了,那对后续数字而言,加sumable_max是可以更大的(我在说什么,反正就是这个意思),否则不如直接重开。
找最小的子数组和时就完全反过来:保留全局最小和global_min+可加最小和sumable_min或0,如果新数字+sumable_min<global_min就更新global_min;如果新数字+sumable_min>0那就白给,立刻重开。

时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( 1 ) O(1) O(1)

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        global_max=0
        sumable_max=0
        global_min=0
        sumable_min=0
        for i in nums:
            sumable_max+=i
            global_max=max(global_max,sumable_max)
            sumable_max=max(0,sumable_max)
            
            sumable_min+=i
            global_min=min(global_min,sumable_min)
            sumable_min=min(0,sumable_min)
        return max(abs(global_max),abs(global_min))

官方Java代码:

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int positiveMax = 0, negativeMin = 0;
        int positiveSum = 0, negativeSum = 0;
        for (int num : nums) {
            positiveSum += num;
            positiveMax = Math.max(positiveMax, positiveSum);
            positiveSum = Math.max(0, positiveSum);
            negativeSum += num;
            negativeMin = Math.min(negativeMin, negativeSum);
            negativeSum = Math.min(0, negativeSum);
        }
        return Math.max(positiveMax, -negativeMin);
    }
}

3. 前缀和

前缀和指的是在数组最前面加个0,从第1个数字到当前数字的和,任何子数组和显然都是某2个前缀和的差值,最大的子数组和绝对值显然就是最大前缀和-最小前缀和(如果最小值<0就直接是最大值-最小值,如果最小值>0就用那个0)

Python 3有内置函数:

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        s = list(accumulate(nums, initial=0))  # nums 的前缀和
        return max(s) - min(s)

Java实现的示例:文章来源地址https://www.toymoban.com/news/detail-638093.html

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int n=nums.length;
        int pre=0;
        int max=0;
        int min=0;
        for(int i=0;i<n;i++){
            pre+=nums[i];
            max=Math.max(max,pre);
            min=Math.min(min,pre);
        }
        return max-min;
    }
}

到了这里,关于1749. 任意子数组和的绝对值的最大值的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Python中计算绝对值fabs()函数

    选择题 请问以下Python代码输出的结果是什么? import math A = -10 B = 10 print(math.fabs(A)) print(math.fabs(B)) 选项: A 10.0 10.0 B -10.0 10.0 C 10.0 -10.0 D -10.0 -10.0 问题解析: 1.fabs()的功能是:返回数字的绝对值。 2.使用fabs()需要先导入math模块,通过math.fabs()调用该方法。 3.题目中A为负数,ma

    2023年04月09日
    浏览(35)
  • Eigen 对矩阵的每个元素取绝对值

      使用Eigen库对矩阵的每一个元素进行取绝对值操作非常简单。可以使用array()函数将矩阵转换为数组,然后使用abs()函数对数组中的每个元素取绝对值,最后使用matrix()函数将数组转换回矩阵。下面是一个示例代码:

    2024年02月04日
    浏览(45)
  • 【MATLAB】线性规划问题中的绝对值问题

    在求解线性规划问题中碰到绝对值的情况: m i n z = ∣ x 1 ∣ + 2 ∣ x 2 ∣ + 3 ∣ x 3 ∣ + 4 ∣ x 4 ∣ , min z=|x_1|+2|x_2|+3|x_3|+4|x_4|, min z = ∣ x 1 ​ ∣ + 2∣ x 2 ​ ∣ + 3∣ x 3 ​ ∣ + 4∣ x 4 ​ ∣ , s . t . { x 1 − x 2 − x 3 + x 4 = 0 , x 1 − x 2 + x 3 − 3 x 4 = 1 , x 1 − x 2 − 2 x 3 + 3 x 4 = − 1 2

    2023年04月09日
    浏览(81)
  • 概率论习题之标准正态绝对值的期望

    一、主要注意的点 E ∣ X ∣ = 2 Π 计算 : E ∣ X ∣ = ∫ − ∞ + ∞ ∣ X ∣ f ( x ) d x E Z = E ∣ x − μ ∣ E|X|={sqrt{frac{2}{Pi}} }\\\\ 计算:E|X|=displaystyle int^{+infty}_{-infty}{|X|f(x)dx}\\\\ EZ=E|x-mu| E ∣ X ∣ = Π 2 ​ ​ 计算 : E ∣ X ∣ = ∫ − ∞ + ∞ ​ ∣ X ∣ f ( x ) d x EZ = E ∣ x − μ ∣ 二、

    2024年03月14日
    浏览(76)
  • C++力扣题目530--二叉搜索树的最小绝对值

    给你一个二叉搜索树的根节点  root  ,返回  树中任意两不同节点值之间的最小差值  。 差值是一个正数,其数值等于两值之差的绝对值。 示例 1: 示例 2: 树中节点的数目范围是  [2, 104] 0 = Node.val = 105 题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。 注意

    2024年02月02日
    浏览(46)
  • Leetcode19-差的绝对值为K的数对数目(2006)

    给你一个整数数组 nums 和一个整数 k ,请你返回数对 (i, j) 的数目,满足 i j 且 |nums[i] - nums[j]| == k 。 |x| 的值定义为: 如果 x = 0 ,那么值为 x 。 如果 x 0 ,那么值为 -x 。 示例 1: 输入:nums = [1,2,2,1], k = 1 输出:4 解释:差的绝对值为 1 的数对为: [1,2,2,1] [1,2,2,1] [1,2,2,1] [1,

    2024年01月15日
    浏览(50)
  • C# Math和Mathf的使用(小数取整、四舍五入、取绝对值等)

    在C#中我们做一些数学计算时,常会见到Math和Mathf的使用。到底使用哪个,它们有什么区别? 首先了解下它们的定义: Math:是C#中封装好的用于数学计算的一个工具类,命名空间是System; Mathf:是Unity中封装好的用于数学计算的一个工具结构体,命名空间是UnityEngine。 事实上,

    2024年02月07日
    浏览(44)
  • 倍福位置记忆--TwinCAT对绝对值编码器溢出圈数的处理--以汇川IS620N为例

    首先配置伺服,如下所示: 根据伺服手册和编码器反馈的数值可知,其每转脉冲数,和最大的记忆圈数: 型号:IS620N 编码器位数:8388608 最大:2149498568 最小:-2149498568 推出最大圈数为256 2=512圈 因此可以得到 汇川编码器结构组成: 共32位:其中精度站23位,圈数占9位,所以

    2024年02月14日
    浏览(46)
  • 【华为OD统一考试B卷 | 100分】乱序整数序列两数之和绝对值最小(C++ Java JavaScript Python)

    华为OD统一考试A卷+B卷 新题库说明 2023年5月份,华为官方已经将的 2022/0223Q(1/2/3/4)统一修改为OD统一考试(A卷)和OD统一考试(B卷)。 你收到的链接上面会标注A卷还是B卷。请注意:根据反馈,目前大部分收到的都是B卷。但是仍有概率抽到A卷。 A卷对应2023的新题库(2022Q4 2

    2024年02月09日
    浏览(37)
  • MT6701磁编码器使用指南,14Bit单圈绝对值,I2C stm32 HAL库读角度,兼容AS5600

      MT6701是麦歌恩(MagnTek)公司的磁性角度传感器芯片,提供14Bit 0~360°单圈绝对角度检测,拥有 ABZ/PWM/模拟量/I2C/SSI 等多种信息输出方式,还可根据磁场强度的瞬时变化提供非接触式按压检测功能。能够以较低的成本来替代传统光电编码器,可应用于绝对值角度输出、闭环

    2024年02月02日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包