草庐IT

每日算法之连续子数组的最大和(二)

loongnuts 2023-04-17 原文

JZ85 连续子数组的最大和(二)

题目

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。
1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
2.如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个
3.该题定义的子数组的最小长度为1，不存在为空的子数组，即不存在[]是某个数组的子数组
4.返回的数组不计入空间复杂度计算

方法 动态规划

思路

算法实现

既然是连续子数组，如果我们拿到了当前的和，对于后面一个即将加入的元素，如果加上他这一串会变得更大，我们肯定会加上它，
如果它自己会比加上前面这一串更大，说明从它自己开始连续子数组的和可能会更大。
具体做法：
    step 1：创建动态规划辅助数组，记录到下标i为止的最大连续子数组和，下标为0的时候，肯定等于原数组下标为0的元素。
    step 2：准备左右区间双指针记录每次连续子数组的首尾，再准备两个双指针记录最大和且区间最长的连续子数组的首尾。
    step 3：遍历数组，对于每个元素用上述状态转移公式记录其dp值，更新区间首尾（如果需要）。
    step 4：出现一个最大值。且区间长度更大的时候，更新记录最长区间的双指针。
    step 5：根据记录的最长子数组的位置取数组。

代码

package mid.JZ85连续子数组的最大和2;

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray(int[] array) {
        // write code here
        if (array.length == 1) return array;
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int max = dp[0];
        //滑动区间
        int left = 0, right = 0;
        //记录最长区间
        int resl = 0, resr = 0;
        for (int i = 1; i < array.length; i++) {
            right++;
            dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
            if (dp[i - 1] + array[i] < array[i]) {
                //如果左边加起来还没有这个值大，那么重新定义left为这个值
                left = right;
            }
            if (dp[i] > max || dp[i] == max && (right - left + 1) > (resr - resl + 1)) {
                max = dp[i];
                resl = left;
                resr = right;
            }
        }

        int[] res = new int[resr - resl + 1];
        for (int i = resl; i <= resr; i++) {
            res[i - resl] = array[i];
        }
        return res;
    }
}
每日子数arrayint的Java

有关每日算法之连续子数组的最大和(二)的更多相关文章

  1. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2

    我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

  2. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  3. ruby - 鸭子输入字符串、符号和数组的优雅方式？ - 2

    这是针对我无法破坏的现有公共(public)API，但我确实希望对其进行扩展。目前，该方法采用字符串或符号或任何其他在作为第一个参数传递给send时有意义的内容我想添加发送字符串、符号等列表的功能。我可以只使用is_a吗？数组，但还有其他发送列表的方法，这不是很像ruby​​。我将调用列表中的map，所以第一个倾向是使用respond_to?:map。但是字符串也会响应:map，所以这行不通。 最佳答案 如何将它们全部视为数组？String的行为与仅包含String的Array相同:deffoo(obj,arg)[*arg].eac

  4. ruby - 是否有内置的 Ruby 1.8.7 将数组拆分为相同大小的子数组？ - 2

    我已经开始了:defsplit_array(array,size)index=0results=[]ifsize>0whileindex如果我在[1,2,3,4,5,6]上运行它，比如split_array([1,2,3,4,5,6],3)它将产生这个数组:[[1,2,3],[4,5,6]]。在Ruby1.8.7中是否已经有可用的东西可以做到这一点？ 最佳答案 [1,2,3,4,5,6].each_slice(3).to_a#=>[[1,2,3],[4,5,6]]对于1.8.6:require'enumerator'[1,2,3,4

  5. ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2

    我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night

  6. ruby - 将 ruby​​ 哈希转换为数组的最佳方法是什么 - 2

    我有一个像这样的ruby​​散列{"stuff_attributes"=>{"1"=>{"foo"=>"bar","baz"=>"quux"},"2"=>{"foo"=>"bar","baz"=>"quux"}}}我想把它变成一个看起来像这样的散列{"stuff_attributes"=>[{"foo"=>"bar","baz"=>"quux"},{"foo"=>"bar","baz"=>"quux"}]}我还需要保留键的数字顺序，并且键的数量是可变的。上面是super简化的，但我在底部包含了一个真实的例子。执行此操作的最佳方法是什么？附言还需要递归就递归而言，这是我们可以假设的:1)

  7. ruby - 如何用 Nokogiri 解析连续的标签？ - 2

    我有这样的HTML代码:Label1Value1Label2Value2...我的代码不起作用。doc.css("first").eachdo|item|label=item.css("dt")value=item.css("dd")end显示所有首先标记，然后标记标签，我需要“标签:值” 最佳答案 首先，您的HTML应该有和中的元素:Label1Value1Label2Value2...但这不会改变您解析它的方式。你想找到s并遍历它们，然后在每个你可以使用next_element得到;像这样:doc=Nokogiri::HTML(

  8. ruby - 我可以从 Ruby 中的系统调用中获得连续输出吗？ - 2

    当您在Ruby脚本中使用系统调用时，您可以像这样获得该命令的输出:output=`ls`putsoutput这就是thisquestion是关于。但是有没有办法显示系统调用的连续输出？例如，如果您运行此安全复制命令，以通过SSH从服务器获取文件:scpuser@someserver:remoteFile/some/local/folder/...它显示随着下载进度的连续输出。但是这个:output=`scpuser@someserver:remoteFile/some/local/folder/`putsoutput...不捕获该输出。如何从我的Ruby脚本中显示正在进行的下载进度？

  9. ruby - 获取数组中值的最大连续出现次数 - 2

    下面有没有更优雅的方法来实现这个:输入:array=[1,1,1,0,0,1,1,1,1,0]输出:4我的算法:streak=0max_streak=0arr.eachdo|n|ifn==1streak+=1elsemax_streak=streakifstreak>max_streakstreak=0endendputsmax_streak 最佳答案 类似于w0lf'sanswer,但通过从chunk返回nil来跳过元素:array.chunk{|x|x==1||nil}.map{|_,x|x.size}.max

  10. arrays - 检查连续数字 - 2

    我有一个整数数组m。我正在寻找一种方法来检查m的元素是否连续。有没有办法测试连续数字？我想出了这段代码，旨在在数组长度为四时工作:m.count==4&&(m.max-m.min)==3对于[1,1,1,4]或[0,0,0,3]错误地返回true。 最佳答案 Enumerable有一个非常方便的方法叫做each_cons是这样工作的:[1,2,3,4].each_cons(2).to_a#=>[[1,2],[2,3],[3,4]]也就是说，它会生成每组连续的n元素。在我们的例子中，n是2。当然，顾名思义，它返回一个Enumerato

随机推荐