题目介绍

给定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。

条件组合覆盖

设计测试用例时，使得每个判断语句中条件结果的所有可能组合至少出现一次
测试用例条件：
　　　　　　　A= T　　　 B= T
　　　　　　　A= T 　　　B= F
　　　　　　　A= F　　　 B= T
　　　　　　　A= F 　　　B= F

测试思路

条件组合	执行情况
sum>0 sum>max	sum+=a[i] max=sum
sum>0 sum<=max	sum+=a[i] max不变
sum<0 sum>max	sum=a[i] max=sum
sum<0 sum<=max	sum=a[i] max不变

动态规划算法

假设最大字段和我们设为 M
我们设1−j中包括a[j]最大字段和为 b[j]
即： b[j]=max{0,b[j−1]}+a[j]}
我们求出包括a[i]−a[n]a[i]−a[n]的所有最大字段和后，只需要求出这些最大字段和中最大的那个就可以了！
即： M=maxb[j]1≤j≤n

执行代码

public class MaxArray{
    public static void main(String[] args){ 
        int arr[] = {-2,11,-4,13,-5,-5,-2};
        int result = maxSumArray(arr.length,arr);
        System.out.println("最大子段和为："+result);
        }
    public static int maxSumArray(int len, int[] a){ 
        int sum = 0, max = 0;       
        for (int i = 0; i < len; i++){
            if (sum > 0){
                sum += a[i];
                }
            else{
                sum = a[i];
                }
            if (sum > max){
                max = sum;
                }
            }
            return max;
            }
    }

测试代码

import static org.junit.Assert.*;
import org.junit.Test;
public class Maxtest {
    @Test
    public void ArrayOne() {
        int[] a= {};
        assertEquals(0,new MaxArray().maxSumArray(a.length, a));
    }
    @Test
    public void ArrayTwo() {
        int[] b= {-2,-11,-4,-13,-5,-2};
        assertEquals(0,new MaxArray().maxSumArray(b.length, b));
    }
    @Test
    public void ArrayThree() {
        int[] c= {-2,11,-4,13,-5,-2};
        assertEquals(20,new MaxArray().maxSumArray(c.length, c));
    }
}

执行情况

https://dev.tencent.com/u/dongxiaoqi/p/ruaner/git

优质内容筛选与推荐>>
1、jvm知识点
2、引用 extJs 2.1学习笔记(通信篇)
3、Windows下ORACLE 10g安装与操作图解
4、Android服务端查询数据库操作
5、网络编程