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. 以此类推的话可以得到下表

1. 总结可得如下规律
   

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<sum{        max=sum    }}return max}

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