最大连续子数组和(最大子段和)

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

最大连续子数组和(最大子段和)

一、问题描述

  1. 问题: 给定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 {

    1. public static int maxSubSum1(int []a){
    2. int maxSum=0; int nowSum=0;
    3. for(int i=0;i<a.length;i++){
    4. nowSum=nowSum+a[i];
    5. if(nowSum>maxSum){//更新最大子段和
    6. maxSum=nowSum;
    7. }
    8. if(nowSum<0){//当当前累加和为负数时舍弃,重置为0
    9. nowSum=0;
    10. }
    11. }
    12. return maxSum;
    13. }
    14. public static void main(String[] args){
    15. Scanner sb = new Scanner(System.in);
    16. int n = sb.nextInt();//定义数组个数
    17. int i;
    18. int []a = new int[100];//定义数组最大数据个数
    19. for(i=0;i<n;i++)
    20. a[i]=sb.nextInt();
    21. int result=maxSubSum1(a);
    22. System.out.println("连续子元素的最大和为:"+result);
    23. sb.close();
    24. }

    }

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

判定/条件覆盖

(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}
测试代码为:

  1. package koko;
  2. import static org.junit.Assert.*;
  3. import org.junit.Test;
  4. public class mkmktest {
  5. @Test
  6. public void test1() {
  7. int []a={-1,2,2,3,4,5};
  8. assertEquals(16,mkmk.maxSubSum1(a));
  9. }
  10. @Test
  11. public void test2(){
  12. int []a={-6,-2,13,-7,14,-1,-2,-2};
  13. assertEquals(20,mkmk.maxSubSum1(a));
  14. }
  15. @Test
  16. public void test3(){
  17. int []a={1,2,3,4,1,2};
  18. assertEquals(13,mkmk.maxSubSum1(a));
  19. }
  20. @Test
  21. public void test4(){
  22. int []a={-1,-2,-4,-7,-9};
  23. assertEquals(0,mkmk.maxSubSum1(a));
  24. }
  25. }

测试结果如图所示:
925276-20180331224902795-1363594344.gif
经过测试,四个用例全部正确。

四、程序代码

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

发表评论

表情:
评论列表 (有 0 条评论,61人围观)

还没有评论,来说两句吧...

相关阅读

    相关 连续

    HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。

    相关 连续

    最大连续子数组和 1. 题目描述 输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有

    相关 连续

    题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候

    相关 连续

    题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候