首页 > 其他分享 >53. 最大子数组和

53. 最大子数组和

时间:2024-04-18 23:45:04浏览次数:28  
标签:pre 遍历 前缀 int 53 数组 最大

题目链接:53. 最大子数组和

这个和560. 和为 K 的子数组类似,这种求子数组和用前缀和解决较为简单,前缀和的核心思想是用pre[i]表示[0,i]的子数组和,则[i,j]的子数组和为pre[j]-pre[i-1]。在560中,遍历到j时找pre[j]-pre[i-1]=K的子数组就是找在j之前等于pre[j]-K的前缀和,所以要存储每一步的前缀和。

说回本题,要让子数组和pre[j]-pre[i-1]最大,遍历到j时,pre[j]已经固定了,让pre[i-1]最小即可求出j作为右边界对应的最大子数组和,因此在遍历时要维护一个当前索引之前的最小子数组和的变量,遍历每个索引都可以得到一个将其作为右边界的最小子数组和,最终取其中最大的即可。代码如下:

class Solution {
    public int maxSubArray(int[] nums) {
        int minpre=0;//当前索引j前的最小[0,i](i<j)子数组和
        int res=-10000;
        int pre=0;
        for(int i:nums){
            pre+=i;//统计前缀和            
            res=Math.max(res,pre-minpre);//更新最大子数组和
            minpre=Math.min(minpre,pre);//更新最小前缀子数组和
        }
        return res;
    }
}

标签:pre,遍历,前缀,int,53,数组,最大
From: https://www.cnblogs.com/keaqi/p/18144778

相关文章

  • 1053 住房空置率
    #include<bits/stdc++.h>usingnamespacestd;constintinf=0x3f3f3f3f;#definelllonglongintmain(){ intn,d; doublee;//阈值 intke=0,kong=0;//数量 cin>>n>>e>>d; for(inti=0;i<n;i++){ intcount; cin>>count;......
  • 洛谷题单指南-动态规划1-P1115 最大子段和
    原题链接:https://www.luogu.com.cn/problem/P1115题意解读:计算最大字段和,典型dp问题。解题思路:设a[]表示所有整数,f[i]表示以第i个数结束的最大字段和当f[i-1]>=0时,f[i]=f[i-1]+a[i]否则,f[i]=a[i]因此,递归式为f[i]=max(a[i],f[i-1]+a[i])注意整数可能为负,ans初始......
  • 判断字符串是否包含数组中的元素
    php怎样简易地判断字符串是否包含数组中的元素呢,折腾了一晌未果。从php内置的字符串函数和数组函数,没见到直接的方法,只有自行循环判断。方法一:循环数组,使用strstr函数判断其中元素是否被包含在字符串中,有则退出循环,输出true,没则循环到底,输出false。亮点是代码直观,遇到true就退出......
  • JTCR-数据类型、变量和数组-01
    原始类型Java是强类型语言,在编译时会检查所有变量、表达式的类型是否兼容。Java为数据定义了8种原始类型(primitivetype),分为4组:整型:byte、short、int、long,表示整数。浮点数:float、double,表示小数。字符:char,表示字符集中的元素。Boolean:boolean,表示true/false值。......
  • 线性时间构造最大堆
    堆堆:是一个数组,近似的完全二叉树,除了最底层外,该树是完全充满的.最小堆:A[i]<=A[2i]&&A[i]<=A[2i+1]最大堆:A[i]>=A[2i]&&A[i]>=A[2i+1]下标从1开始算起维护堆max_heapify(A,i):维护最大堆的性质,让A[i]的值逐级下降if2*i<=len(A)andA[2*i]>A[i]:......
  • 后缀数组学习笔记
    定义后缀数组是什么?(下文用\(Suf_S[i]\)表示\(S[i,i+1,\cdots,|S|]\),对\(Suf_T\)同理。并用\(S[l,r]\)表示\(S[l,l+1,\cdots,r]\),对\(T[l,r]\)同理)后缀数组包含两个数组\(rk,sa\)。\(rk[i]\)表示后缀\(Suf_S[i]\)排序后的排名。\(sa[i]\)表示排......
  • ES6中数组的高级用法
    1.箭头函数和数组方法的结合:使用箭头函数结合数组方法可以简化代码:constnumbers=[1,2,3,4,5];//使用箭头函数的map方法constdoubled=numbers.map((num)=>num*2);console.log(doubled);//输出:[2,4,6,8,10]2.解构赋值和数组方法的结合:constpoi......
  • JS 移除对象数组中,属性值全为空的项
    constarray=[{id:1,name:'John',age:25},{id:2,name:'Alice',age:null},{id:3,name:'Bob',age:undefined},{id:4,name:'Eve',age:''},{id:5,name:'',age:......
  • 后缀数组学习笔记
    定义后缀从字符串某个位置i到字符串末尾的子串,定义s的第i个字符为第一个元素的后缀为suf(i)。后缀数组把s的每一个后缀按照字典序排序,后缀数组sa[i]表示排名为i的后缀的起始位置的下标。rk[i]数组代表起始位置为i的后缀的排名。rk[]和sa[]是一一对应关系,互为逆运算,可以相互......
  • P9753 [CSP-S 2023] 消消乐
    好题,该说不说想了半天manacher结果是假的题目链接:P9753[CSP-S2023]消消乐回归正题对于这道题我们应该怎么做呢?难点其实是在于我们如何在O(1)的时间内判断该字符是否符合于是呢我们稍稍的思考一下就可以得到一个事实:xAAxxxAxxA......形如这样的字符串呢一定是合法的......