要求时间复杂度为O(n)，实现最大子序列的和，并找到最大序列的起始位置和终止位置。例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，最大子序列为3, 10, -4, 7, 2， 因此输出为该子数组的和18，开始位置为2，终止位置为6。dp[i]=max{num[i],dp[i-1]}，其中dp[i]表示以i为末尾节点的最大子序列和，具体看接下来的代码，我这边已经写的很详细了。如果大家都什么好的优化或者有什么没考虑到的还请大家积极指出。
package TestProject; import java.util.Scanner; /** * 最大子序列的和，时间复杂度为O(n)，可以查询出最大子序列的开始位置、截止位置、值 * @author xuhui * */ public class MaxSubArray { public static void main(String[] args){ Scanner scanner = new Scanner(System.in); int len = scanner.nextInt();//输入序列的长度 int[] num = new int[len];//初始化数组 int[] dp = new int[len]; for(int i=0;i<len;i++){ num[i] = scanner.nextInt(); dp[i] = num[i]; } int begin = 0;//记录最大序列开始位置 int s = 0;//记录序列子序列的起始位置 int end = 0;//记录最大序列结束的位置 int max_sum = dp[0];//最大序列的和 for(int i=1;i<len;i++){//更新以i为末尾节点的最大最序列值dp[i]=max{num[i],dp[i-1]+num[i]} if(dp[i]<=(dp[i-1]+num[i])){ dp[i]=dp[i-1]+num[i]; }else{//保证末尾节点为i最大子序列的起始位置 s=i; } if(dp[i]>max_sum){ max_sum = dp[i]; end = i; begin = s; } } System.out.print("begin:"+begin+" end:"+end+" max_sum:"+max_sum); } }