本文共 1568 字，大约阅读时间需要 5 分钟。

三种最大子数组和算法的Java实现和比较

代码于2018年12月12日重新更新了一下，因为之前代码上传时有部分丢失。这次，为了防止代码再丢失，我决定把源码的截图也贴上来（节选自《数据结构与算法分析——Java语言版》——Mark Allen Weiss 著 ---冯舜玺 译）。如下图：

第一种算法：运行时间为O(N^3)，这完全取决于第13和14行，它们由一个含于三重嵌套for循环中的O(1)语句组成。第8行上的循环大小为N。

 第二种算法：运行时间为O(N^2)。

 第三种算法：运行时间为O(N log N)。

（1）Java代码

package com.sau.five.algorithmAnalysis;public class MaxSubsequenceSum {		public static int maxSubsequenceSum01(int[] a)  //方法1：时间复杂度n(o^3)	{		int maxSum=0;     //记录最大子数组和		for(int i=0;i
    
     maxSum)				{					maxSum=thisSum;				}			}		return maxSum;	}		public static int maxSubsequenceSum02(int[] a)   //方法2：时间复杂度n(o^2)	{		int maxSum = 0;		for (int i=0; i
     
       maxSum)				{					maxSum = thisSum;				}			}		}		return maxSum;	}		public static int maxSubsequenceSum03(int[] a)   //方法3：时间复杂度n(o)	{		int maxSum=0;		int thisSum=0;		for(int j = 0; j < a.length; j++){		                        thisSum += a[j];                        if(thisSum > maxSum)                        {				maxSum = thisSum;			}			else if(thisSum < 0)			{				thisSum = 0;			}		}		return maxSum;	}		public static void main(String[] args)      //main方法	{		int L = 1000;     //数组长度		long startTime00=System.nanoTime();   //获取程序开始时间		MaxSubsequenceSum mss = new MaxSubsequenceSum();		int[] a = new int[L];		for(int i=0;i
     
    

（2）三种算法运行结果比较

① 数组长度为1000时，运行结果如下图。比较三种算法的运行时间(单位:豪秒)约为 96.23：2.86：0.07，可见第三种算法的运行效率远高于前两种算法。

 

② 数组长度为10000时，运行结果如下图。比较三种算法的运行时间(单位:秒)约为 98.85：0.03：0.0003，而程序总运行时间也不过98.88秒，可见第一种算法几乎占用了程序运行的全部时间。

 

③ 数组长度为100000时，运行结果如下图。调换一下程序的运行顺序，比较三种算法的运行时间(单位:秒)约为   ∞：2.16：0.003，可见当数组长度达到10^6数量级时，第一种算法已经没有实用价值了。