本文共 2194 字，大约阅读时间需要 7 分钟。
dm[i]表示以nums[i]为右端点的最大子序和
class Solution { public int maxSubArray(int[] nums) { int max; int []dm=new int[nums.length]; dm[0]=nums[0]; max=dm[0]; for(int i=1;i 时间复杂度o(n)
给定数组a[n],他的最大子序和分为3种情况:
① a 0 , a 1 . . . . . a n {a_{0},a_{1}.....a_{n}} a0,a1.....an最大子序和为 a 0 , a 1 . . . . . a n / 2 {a_{0},a_{1}.....a_{n/2}} a0,a1.....an/2的最大子序和 ② a 0 , a 1 . . . . . a n {a_{0},a_{1}.....a_{n}} a0,a1.....an最大子序和为 a n / 2 + 1 , a n / 2 + 2 . . . . . a n {a_{n/2+1},a_{n/2+2}.....a_{n}} an/2+1,an/2+2.....an的最大子序和 ③ a 0 , a 1 . . . . . a n {a_{0},a_{1}.....a_{n}} a0,a1.....an最大子序和为 ∑ k = i j a k {\sum_{k=i}^{j}a_{k}} ∑k=ijak,其中 1 ⩽ i ⩽ n / 2 {1\leqslant i \leqslant n/2} 1⩽i⩽n/2, n / 2 ⩽ j ⩽ n {n/2 \leqslant j \leqslant n} n/2⩽j⩽n;令s1= m a x ( ∑ k = i n / 2 a k ) {max(\sum_{k=i}^{n/2}a_{k})} max(∑k=in/2ak)(其中 1 ⩽ i ⩽ n / 2 {1\leqslant i \leqslant n/2} 1⩽i⩽n/2)；s2= m a x ( ∑ k = n / 2 + 1 j a k ) {max(\sum_{k=n/2+1}^{j}a_{k})} max(∑k=n/2+1jak)(其中 n / 2 + 1 ⩽ j ⩽ n {n/2+1\leqslant j \leqslant n} n/2+1⩽j⩽n)； a 0 , a 1 . . . . . a n {a_{0},a_{1}.....a_{n}} a0,a1.....an最大子序和为s1+s2 代码:import org.junit.Test;public class Test1 { //最大子段和问题 @Test public void Test() { int array[]={ -20,11,-4,13,-5,-2}; System.out.println(MaxSum(array,0,array.length-1)); } int MaxSum(int array[],int left,int right){ if(left==right){ return array[left]; }else { int left_sum = MaxSum(array,left,(left+right)/2);//情况① int right_sum = MaxSum(array,(left+right)/2+1,right);//情况② int sum=0,s1=0,s2=0; int i; for(i=(left+right)/2;i>=left;i--){ sum+=array[i]; if(sum>s1) s1=sum; } sum=0; int j; for(j=(left+right)/2+1;j<=right;j++){ sum+=array[j]; if(sum>s2) s2=sum; } sum=s1+s2; //对比三种结果 return java.lang.Math.max(java.lang.Math.max(sum,left_sum),right_sum); } }} 输出:20
T(n)=2*T(n/2)+n => T(n)=nlogn转载地址：http://eplzi.baihongyu.com/