最大子序列求和问题java实现

谁借莪１个温暖的怀抱￠ 2022-05-21 04:57 151阅读 0赞

## 问题 ##

给定一个整数序列，其中包含正负数，求该序列中所有连续子序列的最大和

## 解法1 ##

> 思路：使用暴力解法，将所有可能的结果全部计算出来，然后找出其中的最大子序列  
> 存在问题：具有大量的重复计算  
> 时间复杂度：O(n^3)

java代码：

public static int[] getMaxChildArrayOne(int[] arr){
    
            int[] maxChildArray = null;
    
            int start = 0;//开始位置
            int end = 0;//结束位置
            int maxSum = 0;//最大值
    
            //循环遍历整个数组
            for(int i=0;i<arr.length;i++){
    
                //数组每次计算之后向后移动
                for(int j=i;j<arr.length;j++){
    
                    //记录当前和
                    int thisSum = 0;
    
                    //每次从头开始计算当前数组所有可能的子序列组合
                    //存在大量重复计算
                    for (int k=i;k<=j;k++){
    
                        //计算求和
                        thisSum += arr[k];
    
                        if (thisSum>maxSum){
                            //记录开始位置
                            start=i;
                            //记录结束位置
                            end=k;
                            //更新最大值
                            maxSum = thisSum;
                        }
                    }
                }
            }
            maxChildArray = Arrays.copyOfRange(arr,start,end+1);
            return maxChildArray;
        }

## 解法2 ##

> 思路：由解法一可知，第二个for循环和第三个for循环存在着大量的重复计算，所以可以减少重复计算，去掉一次for循环  
> 比如：计算arr\[0\] 到 arr\[3\] , 上面的解法会计算 arr\[0\] , arr\[0\]+arr\[1\] , arr\[0\] + arr\[1\] +arr\[2\] , arr\[0\] + arr\[1\] +arr\[2\]+arr\[3\] ，后面的每次计算都包含前面已经计算过的值  
> 时间复杂度：O(n^2)

java代码：

public static int[] getMaxChildArrayTwo(int[] arr){
    
            int[] maxChildArray = null;
            int start = 0;
            int end = 0;
            int maxSum = 0;
            for (int i = 0; i < arr.length; i++) {
    
                //当前子序列和
                int thisSum = 0;
                //依次向后移动一位，遍历剩余序列
                for (int k=i;k<arr.length;k++){
    
                    //求和
                    thisSum += arr[k];
    
                    if (maxSum<thisSum){
    
                        start = i;
                        end = k;
                        maxSum = thisSum;
                    }
                }
            }
            maxChildArray = Arrays.copyOfRange(arr,start,end+1);
            return maxChildArray;
    
        }

## 解法3 ##

> 思路： 由每次计算得到的子序列和thisSum ,如果thisSum<= 0,则说明最大子序列一定不包含当前计算的子序列，即可以舍弃掉当前的子序列从下一个重新开始计算  
> 时间复杂度：O(n)

java代码实现

public static int[] getMaxChildArrayThree(int[] arr){
    
            int[] maxChildArray = null;
            int start = 0;
            int end = 0;
            int maxSum = 0;
    
            int thisSum = 0;
    
            //只需要一次遍历
            for (int i = 0; i < arr.length; i++) {
    
                //求和
                thisSum += arr[i];
    
                //前面计算的总和<=0,所以最大子序列不可能包含已经计算过的子序列
                if (thisSum<=0){
                    //最大子序列下标从下个开始计算
                    start = i+1;
                    //当前和置为 0
                    thisSum = 0;
                }
    
                if (thisSum>maxSum){
    
                   //结束位置为当前计算的子序列和的最后一个下标
                    end = i;
                    maxSum = thisSum;
                }
            }
            maxChildArray = Arrays.copyOfRange(arr,start,end+1);
            return maxChildArray;
    
        }