引言：在牛課網(wǎng)刷題時(shí)遇到好多次使用動(dòng)態(tài)規(guī)劃求解最大字段和類似的問題茵瘾，但是每一次都毫無頭緒箱熬，今天趁著復(fù)習(xí)算法央串，將最大字段和好好的腹瀉了一遍：下面是自己的一些簡(jiǎn)單的筆記:
一：?jiǎn)栴}描述：
給定n個(gè)整數(shù)（可能為負(fù)整數(shù)）組成的序列a1,a2,a3…..an举反。求該序列如同
的子段和的最大值

公式.png

/**
     * 三次循環(huán)的方式：
     * 時(shí)間復(fù)雜度為O(n^3)
     * 這種情況是分別計(jì)算從第一數(shù)開始一直加到最后一個(gè)數(shù)的最大值記錄下來
     * 再從第二個(gè)數(shù)開始一直加到最后一個(gè)數(shù)將最大值保存下來指巡；
     * .....
     * 一直到最后只剩最后一個(gè)數(shù)淑履；
     * @param arr
     * @param n
     * @param l
     * @param r
     * @return
     */
    public static int MaxSum(int[] arr,int n,int l,int r){
        int sum = 0;
        for(int i =0;i<n;i++){
            for(int j=i;j<n;j++){
                int temp = 0;
                for(int k=j;k<n;k++){
                    temp+=arr[k];
                    if(temp>sum){
                        sum=temp;
                        l=i;
                        r=j;
                    }
                }
            }
        }
        return sum;
    }

2:在1的基礎(chǔ)上優(yōu)化使其時(shí)間復(fù)雜度縮減至O(n^2)

     /**
     * @param arr       目標(biāo)數(shù)組
     * @param n         目標(biāo)數(shù)組的長(zhǎng)度
     * @param l     最終字段和的起點(diǎn)
     * @param r     最終字段和的終點(diǎn)
     * @return
     */
public int MaxSum(int[] arr,int n,int l,int r){
        int sum=0;
        for(int i=0;i<n;i++){
            int temp = 0;
            for(int j=i;j<n;j++){
                temp+=arr[j];
                if(temp>sum){
                    sum=temp;
                    l=i;
                    r=j;
                }
            }
        }
        return 0;                                                                                                                                                                                                                                                                                                                                                                                                                     
    }

3:使用分治法求解
如果將序列a[1:n]分為長(zhǎng)度相等的兩段a[1:n/2]和a[n/2+1:n];分別求這兩種情況下的最大字段和，則a[1:n]的最大字段和有3種情況：
A:a[1:n]的最大字段和與a[1:n/2]的最大字段和相等
B:a[1:n]的最大字段和與a[n/2+1:n]的最大字段和相等
C:a[1:n]的最大字段和為

求和.png

且1<=i<=n/2,n/2+1<=j<=n.
時(shí)間復(fù)雜度為O(nlogn)

/**
     * 使用分治法求解最大字段和
     * @param arr
     * @param left 序列的最左下標(biāo)
     * @param right 序列的最右下標(biāo)
     * @return
     */
    public int MaxSubSum(int arr[],int left,int right){
        int sum =0;
        if(left==right){
            sum = (arr[left]>0)?arr[left]:0;
        }else{
            int center = (left+right)/2;
              //遞歸求解左右邊序列的最大字段和
            int leftSum = MaxSubSum(arr, left, center);
            int rightSum = MaxSubSum(arr, center+1, right);
            //求左邊子序列的最大字段長(zhǎng)度
            int s1 =0;
            int lefts = 0;
            for(int i=center;i>=0;i--){
                lefts+=arr[i];
                if(lefts>s1){
                    s1 = lefts;
                }
            }
            //求右邊子序列的最大字段長(zhǎng)度
            int s2= 0;
            int rights = 0;
            for(int i=center+1;i<right;i++){
                rights+=arr[i];
                if(s2<rights){
                    s2=rights;
                }
            }
            sum = s1+s2;
            if(sum<leftSum){sum=leftSum;}
            if(sum<rightSum){sum=rightSum;}
        }
    
        return sum;
    } 

4:動(dòng)態(tài)規(guī)劃求解最大字段和：
僅僅在O(n)時(shí)間復(fù)雜度就可以將結(jié)果求出來藻雪；

/**
     * 
     * @param n 序列的長(zhǎng)度
     * @param arr 待求序列
     * @return
     */
    public static int MaxSums(int n,int arr[]){
        int sum = 0;
        //子序列
        int b = 0;
        for(int i=0;i<n;i++){
            if(b>0){
                b+=arr[i];
            }else{
                b=arr[i];
            }
            if(b>sum){
                sum=b;
            }
        }
        return sum;
    }