golang中怎么利用leetcode连续数列

本篇文章为大家展示了golang中怎么利用leetcode连续数列,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。

让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:申请域名、网络空间、营销软件、网站建设、太原网站维护、网站推广。

给定一个整数数组(有正数有负数),找出总和最大的连续数列,并返回总和。

示例:

输入:[-2,1,-3,4,-1,2,1,-5,4]

输出:6

解释:连续子数组 [4,-1,2,1] 的和最大,为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

解题思路

解题方案一 (动态规划)

思路

假设数组名称为arr,结果数组为result

  1. 当只有一个数字的时候,最大的连续数列只能是这个数字,所以序号为0的位置,最大值为-2,则有result[0] = arr[0]

  2. 当有两个数字时,有两种情况

    1. 保留前边的序列,此时值为result[0] + arr[1]=

    2. 不保留前边的序列,此时值为1,即arr[1]

    3. 此时选取最大值的话为1

  3. 到第三个数字时

    1. 保留前边的序列,值为result[1] + arr[2] = 1 + -3 = -2

    2. 不保留前边的序列,值为arr[2] = -3

    3. 此时选取最大值的话为-3

  4. 以此类推的话可以得到下表

序号012345678
数值(arr数组)-21-34-121-54
保留前边的序列
-1-4-135615
不保留前边的序列
1-34421-54
最大值(result数组)-21-3445614
  1. 总结可得如下规律
    golang中怎么利用leetcode连续数列

  2. 最终只需取得result[]中值最大的数即为结果

代码
   public static int maxSubArray(int[] arrs) {
       int len = arrs.length;
       int maxNum = arrs[0];
       int[] result = new int[arrs.length];
       result[0] = maxNum;
       for (int i = 1; i < len; i++) {
           int a = result[i - 1] + arrs[i];  //保留前边的序列
           int b = arrs[i];  //不保留前边的序列

           int curMax = Math.max(a, b);
           result[i] = curMax;

           if (curMax > maxNum) {
               maxNum = curMax;
           }
       }
       return maxNum;
   }
代码优化

由于上述过程中,创建了result数组,但是实际上每次循环时,当前数字计算完之后就没有其他用处了,所以此处可以使用arrs数组作为result数组来用,优化后如下

    public static int maxSubArray(int[] arrs) {
       int len = arrs.length;
       int maxNum = arrs[0];
       for (int i = 1; i < len; i++) {
           int a = arrs[i - 1] + arrs[i];  //保留前边的序列
           int b = arrs[i];  //不保留前边的序列

           int curMax = Math.max(a, b);
           arrs[i] = curMax;

           if (curMax > maxNum) {
               maxNum = curMax;
           }
       }
       return maxNum;
   }

代码实现

func maxSubArray(nums []int) int {sum:=0max:=0for i,n:=range nums{    if i==0{        max=n        sum=n        continue    }    if sum+n>n{        sum+=n    }else{        sum=n    }    if max 

上述内容就是golang中怎么利用leetcode连续数列,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注创新互联行业资讯频道。


网页标题:golang中怎么利用leetcode连续数列
转载来于:http://bzwzjz.com/article/jeocci.html

其他资讯

Copyright © 2007-2020 广东宝晨空调科技有限公司 All Rights Reserved 粤ICP备2022107769号
友情链接: 成都网站设计 营销型网站建设 成都网站建设 成都网站制作 手机网站制作 成都网站设计 攀枝花网站设计 成都品牌网站设计 公司网站建设 品牌网站建设 LED网站设计方案 成都网站建设 手机网站设计 成都网站建设 四川成都网站建设 成都定制网站建设 成都网站建设 上市集团网站建设 网站建设方案 定制网站设计 成都网站设计 重庆网站建设