今天上课王建民老师讲了关于代码的测试，代码要一个一个模块的进行测试，而不是堆积在一起，这样既烦乱又容易出现错误。其次讲了代码的三个重要知识点，格式，变量名和注释。
课后小测中，题目为 一个有n个元素的数组，这n个元素可以是正数也可以是负数，数组中连续的一个或多个元素可以组成一个连续的子数组，一个数组可能有多个这种连续的子数组，求子数组和的最大值。
一种方法是找出所有子数组的和，然后取其最大值。
package xiaozhaobishi;
import java.util.Scanner;
public class maxSubArray {
public static int maxSubArrayMethodOne(int arr[]){
int n = arr.length;
int ThisSum=0,MaxSum=0,i,j,k;
for(i=0;i<n;i++){
for(j=i;j<n;j++){
ThisSum=0; //重新累加子数组
for(k=i;k<j;k++){
ThisSum+=arr[k];
}
if(ThisSum>MaxSum){
MaxSum=ThisSum;
}
}
}
return MaxSum;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int number=Integer.parseInt(sc.next());
//number表示数组的长度
int[] num=new int[number];
//对数组元素循环赋值
for(int i=0;i<number;i++){
num[i]=(int)sc.nextInt();
}
System.out.println(maxSubArrayMethodOne(num));
}
}
一种方法是用两个for循环完成。
package xiaozhaobishi;
import java.util.Scanner;
public class maxSubArray {
public static int maxSubArrayMethodTwo(int arr[]){
int size =arr.length;
int maxSum=Integer.MIN_VALUE;
for(int i=0;i<size;i++){
int sum=0;
for(int j=i;j<size;j++){
sum+=arr[j];
if(sum>maxSum){
maxSum=sum;
}
}
}
return maxSum;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int number=Integer.parseInt(sc.next());
//number表示数组的长度
int[] num=new int[number];
//对数组元素循环赋值
for(int i=0;i<number;i++){
num[i]=(int)sc.nextInt();
}
System.out.println(maxSubArrayMethodTwo(num));
}
}
另外一种方法便是动态规划方法（网上所找）
可以采用动态规划的方法来降低算法的时间复杂度，实现思路如下：
首先可以根据数组的最后一个元素[n-1]与最大子数组的关系分为以下3种情况：
1）最大子数组的包含arr[n-1],即以arr[n-1]结尾。
2）arr[n-1]单独构成最大子数组。
3）最大子数组不包含arr[n-1]，那么求arr[1,…,n-1]的最大子数组可以转换为求arr[1,…,n-2]的最大子数组。
通过以上分析可以得出如下结论：假设已经计算出(arr[0],…,arr[i-1])最大的一段数组和为All[i-1]，同时也计算出(arr[0],…,arr[i-1])中包含arr[i-1]的最大的一段数组和为End[i-1]，则可以得出如下关系：All[i-1]=max{arr[i-1]，End[i-1]，All[i-2]}。利用这个公式和动态规划的思想可以得到如下代码：
package xiaozhaobishi;
import java.util.Scanner;
public class maxSubArray {
public static int max(int m,int n){
return m>n ? m :n;
}
public static int maxSubArrayMethodThree(int arr[]){
int n=arr.length;
int End[]=new int[n];
int All[]=new int[n];
End[n-1]=arr[n-1];
All[n-1]=arr[n-1];
End[0]=All[0]=arr[0];
for(int i=1;i<n;i++){
End[i]=max(End[i-1]+arr[i],arr[i]);
All[i]=max(End[i],All[i-1]);
}
return All[n-1];
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int number=Integer.parseInt(sc.next());
//number表示数组的长度
int[] num=new int[number];
//对数组元素循环赋值
for(int i=0;i<number;i++){
num[i]=(int)sc.nextInt();
}
System.out.println(maxSubArrayMethodThree(num));
}
}