软件工程第三次作业

最大子数列问题在计算机科学中，最大子数列问题的目标是在数列的一维方向找到一个连续的子数列，使该子数列的和最大。例如，对一个数列 −2, 1, −3, 4, −1, 2, 1, −5, 4，其连续子数列中和最大的是 4, −1, 2, 1, 其和为6。该问题最初由布朗大学的Ulf Grenander教授于1977年提出，当初他为了展示数字图像中一个简单的最大似然估计模型。不久之后卡内基梅隆大学的Jay Kadane提出了该问题的线性算法。（Bentley 1984）。 --wikipedia《最大子数列问题》

0X00 编写线性算法

Code0

Kadane算法，时间复杂度为\(O(n)\)。递推公式 \(dp[i] = max ( dp[i-1] + arr[i] , arr[i] )\)

public static int maxSubarray(int[] arr){
    int len = arr.length;
    int dp = 0 , res = arr[0];
    for(int i = 0 ; i < len ; ++i){
        dp += arr[i];
        res = dp > res ? dp : res;
        if(dp < 0) dp = 0;
    }
    return res;
}

0X01 编写用于对拍的算法

\(O(n^2)\)算法。第一层循环枚举子数组起点，第二层循环枚举子数组终点。

public static int Calu(int[] arr){
    int ans = arr[0], res;
    int len = arr.length;
    for(int i=0;i<len;++i){
        res = 0;
        for(int j=i;j<len;++j){
            res += arr[j];
            ans = ans >  res ? ans : res;
        }
    }
    return ans;
}

0X02 编写随机数组生成器

随机数组的最大长度定为1000，方便\(O(n^2)\)算法快速对拍。
随机数生成的种子为\(19260817\)。

private static Random it = new Random(19260817); // 随机数对象
    
public static int intRand(int min,int max){ // 返回一个范围在[min,max]的随机数
    return min + it.nextInt( max - min + 1 ) + min; 
}

public static int[] intarrGen(int mod){ //生成随机数组
    int len = intRand(1,mod);
    int[] arr = new int[len];
    for(int i = 0 ; i < len; ++i){
        arr[i] = intRand(-10000,100000);
    }
    return arr;
}

0X03 编写测试类

package maxSubArray;

import static org.junit.Assert.*;
import org.junit.*;

public class testSubArr {
    @Test
    public void testNormalArray(){ //作业测试数据
        int arr[] = {-2,11,-4,13,-5,-2};
        int ans = maxSubArr.Calu(arr);
        assertEquals(ans, new maxSubArr().maxSubarray(arr));
    }
    @Test
    public void testNegativesArray(){ //全负整数测试数据
        int arr[] = {-2,-11,-4,-1,-5,-2};
        int ans = maxSubArr.Calu(arr);
        assertEquals(ans, new maxSubArr().maxSubarray(arr));
    }
    @Test
    public void testPositivesArray(){ //全正整数测试数据
        int arr[] = {2,11,4,13,5,2};
        int ans = maxSubArr.Calu(arr);
        assertEquals(ans, new maxSubArr().maxSubarray(arr));
    }
    
    @Test
    public void testRandomArray(){ //多组随机测试数据
        int arr[];
        int ans;
        for(int i=0;i<1000;++i){
            arr = maxSubArr.intarrGen(1000); // 调用随机测试数据生成器
            ans = maxSubArr.Calu(arr);
            assertEquals(ans, new maxSubArr().maxSubarray(arr));
        }
    }
}

Code1

加上随机生成的数据，能够完成语句覆盖、判定覆盖、条件覆盖、判定/条件覆盖、条件组合覆盖的要求。

0X04 测试

右键"testSubArr.java"，Run as -> 1 JUnit Test ，Ok