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連續數列，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。