最大连续子数组和--dp

最大连续子数组和

　　问题：给定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。

题意：

　　含有N个数的数组，求最大的连续子段的和，动态规划:递推公式是dp[i] = max{dp[i-1] + arr[i],arr[i]}

参考代码：

　　Github地址：点我一下

 1 public class dp {

 2     public int max_string(int arr[]){

 3         if(arr == null || arr.length <= 0){

 4             return 0;

 5         }

 6         int len = arr.length;

 7         int Max=0x8000000;

 8         int this_max=0;

 9         for(int i=0; i<len; i++){

10             Max = Math.max(Max, this_max=this_max+arr[i]>0?this_max+arr[i]:0);

11         }

12         return Max;

13     }

单元测试

1.覆盖标准

　　条件组合覆盖：使得每个判定中条件的各种可能组合都至少出现一次。

2.流程图：

3.测试代码：

 1 public class dp_test {

 2     dp d = null;

 3     @Before

 4     public void set_up(){

 5         d = new dp();

 6     }

 7     @Test

 8     public void test_1() {

 9         int arr[]={-1,-1,-1,-1,-1};

10         Assert.assertEquals(d.max_string(arr), 0);

11     }

12     @Test

13     public void test_2() {

14         int arr[]={0,0,0,0,0};

15         Assert.assertEquals(d.max_string(arr), 0);

16     }

17     @Test

18     public void test_3() {

19         int arr[]={1,2,3,4,5};

20         Assert.assertEquals(d.max_string(arr), 15);

21     }

22     @Test

23     public void test_4() {

24         int arr[]={-2,11,-4,13,-5,-2};

25         Assert.assertEquals(d.max_string(arr), 20);

26     }

27     @Test

28     public void test_5() {

29         int arr[]={1,2,-4,8,-1};

30         Assert.assertEquals(d.max_string(arr), 8);

31     }

32

33 }

4.测试结果

巴特西

最大连续子数组和--dp

最大连续子数组和

单元测试

最新文章

热门文章