golang中怎么利用leetcode連續(xù)數(shù)列

本篇文章為大家展示了golang中怎么利用leetcode連續(xù)數(shù)列，內(nèi)容簡(jiǎn)明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。

給定一個(gè)整數(shù)數(shù)組（有正數(shù)有負(fù)數(shù)），找出總和最大的連續(xù)數(shù)列，并返回總和。

示例：

輸入：[-2,1,-3,4,-1,2,1,-5,4]

輸出：6

解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。

進(jìn)階：

如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

解題思路

解題方案一 (動(dòng)態(tài)規(guī)劃)

思路

假設(shè)數(shù)組名稱為arr，結(jié)果數(shù)組為result

1. 當(dāng)只有一個(gè)數(shù)字的時(shí)候,最大的連續(xù)數(shù)列只能是這個(gè)數(shù)字，所以序號(hào)為0的位置，最大值為-2,則有result[0] = arr[0]

2. 當(dāng)有兩個(gè)數(shù)字時(shí),有兩種情況

1. 保留前邊的序列，此時(shí)值為result[0] + arr[1]=

2. 不保留前邊的序列,此時(shí)值為1,即arr[1]

3. 此時(shí)選取最大值的話為1

3. 到第三個(gè)數(shù)字時(shí)

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

2. 不保留前邊的序列，值為arr[2] = -3

3. 此時(shí)選取最大值的話為-3

4. 以此類推的話可以得到下表

1. 總結(jié)可得如下規(guī)律
   

2. 最終只需取得result[]中值最大的數(shù)即為結(jié)果

代碼

   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;
    }

代碼優(yōu)化

由于上述過程中,創(chuàng)建了result數(shù)組,但是實(shí)際上每次循環(huán)時(shí),當(dāng)前數(shù)字計(jì)算完之后就沒有其他用處了，所以此處可以使用arrs數(shù)組作為result數(shù)組來用，優(yōu)化后如下

    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;
    }

代碼實(shí)現(xiàn)

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}

上述內(nèi)容就是golang中怎么利用leetcode連續(xù)數(shù)列，你們學(xué)到知識(shí)或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備，歡迎關(guān)注億速云行業(yè)資訊頻道。