【答案解析】问题描述：一个有n个元素的数组，这n个元素可以是正数也可以是负数，数组中连续的一个或多个元素可以组成一个连续的子数组，一个数组可能有多个这种连续的子数组，求子数组和的最大值，例如：对于数组{1，-2，4，8，-4，7，-1，-5}而言，其最大和的子数组为{4，8，-4，7}，最大值为15。
方法一：“蛮力”法
最简单也是最容易想到的方法就是找出所有子数组，然后求出子数组的和，在所有子数组的和中取最大值。
public class Test{
public static int maxSubArray(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){
int[]array={1, -2, 4, 8, -4, 7, -1, -5};
System.out.println(maxSubArray(array));
}
}
程序运行结果为：
15
以上这个算法的时间复杂度为O(n^3)，显然效率太低，通过对该算法进行分析发现，许多子数组都重复计算了，鉴于此，下面给出一种优化的方法。
方法二：重复利用已经计算的子数组和
例如Sum[i, j]=Sum[i, j-1]+arr[j]，采用这种方法可以省去计算Sum[i, j-1]的时间，因此可以提高程序的效率。示例如下：
public class Test{
public static int maxSubArray(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){
int[]array={1, -2, 4, 8, -4, 7, -1, -5};
System.out.println(maxSubArray(array));
}
}
以上这个算法的时间复杂度为O(n^2)。
方法三：动态规划方法
可以采用动态规划的方法来降低算法的时间复杂度，实现思路如下。
首先可以根据数组的最后一个元素arr[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]}。利用这个公式和动态规划的思想可以得到如下代码：
public class Test{
public static int max(int m, int n){
return m＞n?m:n;
}
public static int maxSubArray(int art[]){
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){
int[]array={1, -2, 4, 8, -4, 7, -1, -5};
System.out.println(rraxSubArray(array));
}
}
与前面几种方法相比，这种方法的时间复杂度为O(n)，显然效率更高，但是由于在计算的过程中额外申请了两个数组空间，因此该算法的空间复杂度也为O(n)。
方法四：优化的动态规划方法
方法三中每次只用到End[i-1]与All[i-1]，而不是整个数组中的值，因此可以定义两个变量来保存End[i-1]与All[i-1]的值，并且可以反复利用，这样就可以在保证时间复杂度为O(n)的同时降低空间复杂度。示例如下：
public class Test{
public static int max(int m, int n){
return m＞n?m:n;
}
public static int maxSubArray(int arr[]){
int n=arr.length;
int nAll=arr[0]; //有n个数字数组的最大子数组和
int nEnd=arr[0]; //有n个数字数组包含最后一个元素的子数组的最大和
for(int i=1; i＜n; ++i){
nEnd=max(nEnd+arr[i], arr[i]);
nAll=max(nEnd, nAll);
}
return nAll;
}
public static void main(String[]args){
int[]array={1, -2, 4, 8, -4, 7, -1, -5};
System.out.println(maxSubArray(array));
}
}
在知道子数组的最大和之后，如何才能确定最大子数组的位置呢?为了得到最大子数组的位置，首先介绍另外一种计算最大子数组和的方法。在方法三中，通过对公式End[i]=max(End[i-1]+arr[i]，arr[i])的分析可以看出，当End[i-1]＜0时，End[i]=array[i]，其中，End[i]表示包含array[i]的子数组和，如果某一个值使得End[i-1]＜0，那么就从arr[i]重新开始。示例如下：
public class Test{
private static int begin=0; //记录最大子数组的起始位置
private static int end=0; //记录最大子数组的结束位置
public static int maxSubArray(int arr[]){
int maxSum=Integer.MIN_VALUE; //子数组最大值
int nSum=0; //包含子数组最后一位的最大值
int nStart=0;
for(int i=0; i＜arr.length; i++){
if(nSum＜0){
nSum=arr[i];
nStart=i;
}
else{
nSum+=arr[i];
}
if(nSum＞maxSum){
maxSunl=nSum;
begin=nStart;
end=i;
}
}
return maxSum;
}
public static void main(String[]args){
int[]array={1, -2, 4, 8, -4, 7, -1, -5};
System.out.println("max="+maxSubArray(array));
System.out.println("begin="+begin+", end="+end);
}
}程序运行结果为：
max=15
begin=2, end=5