最大连续子数组和（最大子段和）
一、问题描述
问题描述： 给定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。
二、题目分析
本次使用Java语言编写程序，使用eclipse编译器。给定一组随机数，存入数组中，然后求出其最大连续子数组和。我使用了“在线算法”算法来编程。因为这个算法看着简单，只需要一层循环，程序容易读懂。具体算法可以参考这篇博客
三、源代码
package sum;
import java.util.Scanner;
public class Sum
{
public static int getsum(int array[])
{
int i=0;
int newSum = 0;
int FinSum = 0;
int index = array.length;
for(i=0;i<index;i++)
{
newSum = newSum + array[i];
if(newSum > FinSum)
{
FinSum = newSum;
}
if(newSum < 0)
{
newSum = 0;
}
}
return FinSum;
}
public static void main(String[] args)
{
int index = 0;
int array[] = new int[100];
Scanner in = new Scanner(System.in);
/*
输入数组的元素
*/
while(in.hasNextInt())
{
array[index++] = in.nextInt();
}
int Ans = getsum(array);
System.out.println("最大子数组和为："+Ans);
}
}
四、运行结果
五、测试用例
-
1、关键程序流程图
-
2、覆盖标准：条件组合覆盖
newSum>FinSum & newSum<0（即AC）
newSum>FinSum & newSum>=0（即AD）
newSum<=FinSum & newSum<0（即BC）
newSum<=FinSum & newSum>=0（即BD） -
3、测试用例
数组元素：{1,2,3,4,5}，执行路径：AD，覆盖条件：newSum>FinSum & newSum>=0
数组元素：{-1，-2，-3，-4,-5}，执行路径：BC，覆盖条件：newSum<=FinSum & newSum<0
数组元素：{-1，-2,6，-3，-4}，执行元素：BD,覆盖条件：newSum<=FinSum & newSum>=0
注：分析后，执行路径AC无法执行
六、单元测试
- 1、测试程序
package sum;
import static org.junit.Assert.*;
import org.junit.Test;
public class SumTest
{
@Test
public void test1()
{
int input[] = new int[]{1,2,3,4,5};
int output = 15;
assertEquals(output,Sum.getsum(input));
}
@Test
public void test2()
{
int input[] = new int[]{-1,-2,-3,-4,-5};
int output = 0;
assertEquals(output,Sum.getsum(input));
}
@Test
public void test3()
{
int input[] = new int[]{-1,-2,6,-3,4};
int output = 7;
assertEquals(output,Sum.getsum(input));
}
@Test
public void test4()
{
int input[] = new int[]{-2,11,-4,13,-5,-2};
int output = 20;
assertEquals(output,Sum.getsum(input));
}
}
- 2、测试结果
注：测试方法为4个，均通过测试
七、程序链接
https://git.coding.net/long-long-ago/software-task3.git
八、个人感想
在昨天，我用C语言写好了源程序，本以为转换为Java语言很简单。但上手做起来却发现有点棘手的问题。首先，怎么给数组复制。在C语言里可以先初始化数组为Array[100],然后输入数组个数n，最后通过循环依次将数组赋值。但在Java里这样却行不通，我试了很多方法都没成功。百度了一些有关数组的程序，重点看人家是怎么对数组赋值的，我选择了一个我能读懂的程序拿来用。其次，在编写测试类的时候，由于程序的所有操作都堆在一个类中，不会写子类。参考了同学的程序，慢慢改好了主要的代码，然后写测试类就容易很多了。
就发现的这些问题中，我认为原因主要在于自己没有真正理解Java语言，对基本操作也是一知半解，例如如何编写类，使其更加简化；数组不会赋值。在上学期的Java课上，作业也是稀里糊涂的完成了。在接下来的半年，我要继续学Java语言，希望能够理解Java的精髓。同时也要多多编程，更好得理解和掌握Java语言。