动态规划---最大字段和

引言：在牛课网刷题时遇到好多次使用动态规划求解最大字段和类似的问题，但是每一次都毫无头绪，今天趁着复习算法，将最大字段和好好的腹泻了一遍：下面是自己的一些简单的笔记:
一：问题描述：
给定n个整数（可能为负整数）组成的序列a1,a2,a3…..an。求该序列如同
的子段和的最大值

公式.png
的值。
二：解法：
1：暴力解法：列出所有的可能性：

/**
     * 三次循环的方式：
     * 时间复杂度为O(n^3)
     * 这种情况是分别计算从第一数开始一直加到最后一个数的最大值记录下来
     * 再从第二个数开始一直加到最后一个数将最大值保存下来；
     * .....
     * 一直到最后只剩最后一个数；
     * @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的基础上优化使其时间复杂度缩减至O(n^2)

     /**
     * @param arr       目标数组
     * @param n         目标数组的长度
     * @param l     最终字段和的起点
     * @param r     最终字段和的终点
     * @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]分为长度相等的两段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.
时间复杂度为O(nlogn)

/**
     * 使用分治法求解最大字段和
     * @param arr
     * @param left 序列的最左下标
     * @param right 序列的最右下标
     * @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);
            //求左边子序列的最大字段长度
            int s1 =0;
            int lefts = 0;
            for(int i=center;i>=0;i--){
                lefts+=arr[i];
                if(lefts>s1){
                    s1 = lefts;
                }
            }
            //求右边子序列的最大字段长度
            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:动态规划求解最大字段和：
仅仅在O(n)时间复杂度就可以将结果求出来；

/**
     * 
     * @param n 序列的长度
     * @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;
    }