最大连续子数组和（最大子段和）

桃扇骨 2023-06-01 06:23 2阅读 0赞

# 最大连续子数组和（最大子段和） #

## 一、问题描述 ##

问题： 给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0，依此定义，所求的最优值为： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2)时，最大子段和为20。

## 二、程序设计与实现 ##

### 1、程序设计思想 ###

*  枚举法：确定每个字段和的开始位置（从1~n），然后计算该位置以后的每一个长度的字段和，随时更新最大字段和，但此法在数据量逐渐多时，运行的时间也随之暴涨，此法的时间复杂度为O(n^2)。
 *  分治法：通过分治的思想求最大子段和，将数组分平均分为两个部分，则最大子段和会存在于三种情况下：  
    （1）、最大子段和出现在左端，可用递归求的；  
    （2）、最大子段和出现在右端，可用递归求得；  
    （3）、最大字段和出现在中间，则先计算出左端的最大字段和s1, 再计算出右端的最大字段和s2,则s1+s2为所求。
 *  动态规划：运用了动态规划的思想来解决最大子段和问题：  
    通过遍历累加这个数组元素，定时的更新最大子段和，  
    如果当前累加数为负数，直接舍弃，重置为0,然后接着遍历累加。  
    时间复杂度:O(n)，此法运行速度最快，所以用此法进行编译程序。
    
    ### 2、程序编译 ###

package koko;
    import java.util.*; 
    public class mkmk {
        public static int maxSubSum1(int []a){
               int maxSum=0; int nowSum=0;
               for(int i=0;i<a.length;i++){
                   nowSum=nowSum+a[i];
                   if(nowSum>maxSum){//更新最大子段和
                       maxSum=nowSum;
                   }
                   if(nowSum<0){//当当前累加和为负数时舍弃，重置为0
                       nowSum=0;
                   }
               }   
               return maxSum;
           }
        public static void main(String[] args){ 
            Scanner sb = new Scanner(System.in);  
            int n = sb.nextInt();//定义数组个数
            int i;
            int []a = new int[100];//定义数组最大数据个数
            for(i=0;i<n;i++)
                a[i]=sb.nextInt();
            int result=maxSubSum1(a);
            System.out.println("连续子元素的最大和为："+result);
            sb.close();
        }
    }

## 三、代码运行测试及测试用例选择 ##

### 判定/条件覆盖 ###

（1）nowSum>maxSum nowSum<0 测试用例：\{-1，2，2，3，4，5\}  
（2）nowSum<=maxSum nowSum>=0测试用例：\{-6,-2,13,-7,14,-1,-2,-2\}  
（3）nowSum>maxSum nowSum>=0测试用例：\{1，2，3，4，1，2\}  
（4）nowSum<=maxSum nowSum<0测试用例：\{-1，-2，-4，-7，-9\}  
测试代码为：

package koko;
    
    import static org.junit.Assert.*;
    
    import org.junit.Test;
    
    public class mkmktest {
    
        @Test
        public void test1() {
            int []a={-1,2,2,3,4,5};
            assertEquals(16,mkmk.maxSubSum1(a));
        }
        @Test
        public void test2(){
            int []a={-6,-2,13,-7,14,-1,-2,-2};
            assertEquals(20,mkmk.maxSubSum1(a));
        }
        @Test
        public void test3(){
            int []a={1,2,3,4,1,2};
            assertEquals(13,mkmk.maxSubSum1(a));
        }
        @Test
        public void test4(){
            int []a={-1,-2,-4,-7,-9};
            assertEquals(0,mkmk.maxSubSum1(a));
        } 
    
    }

测试结果如图所示：  
![925276-20180331224902795-1363594344.gif][]  
经过测试，四个用例全部正确。

## 四、程序代码 ##

转载于:https://www.cnblogs.com/zt960515/p/8687001.html

[925276-20180331224902795-1363594344.gif]: /images/20230601/8e14963ebae348b497924be3ef77a11d.png