LeetCode53、最大子序和（分治法動态規劃）

題目描述

暴力法

class Solution {
    public int maxSubArray(int[] a) {

    int n = a.length;
    if(n==1){
        return a[0];
    }
    int max=Integer.MIN_VALUE,esti=0;
	for(int i=0;i<n;i++){//以a[i]開頭的子段求和，取最大值 
		int sub= 0; 
		for(int j=i;j<n;j++){//a[i]~a[j]子段 
				sub+=a[j];
				if(sub>max){
					max = sub;
					
				}	
		}
    }
    return max;

    }
}
           

分治法

class Solution {
    public int maxSubArray(int[] a) {
        return MaxSubsum(a,0,a.length-1);
    }
   public int MaxSubsum(int []a,int left,int right){
	int sum;
	if(left==right)
		sum=a[left];
	else{
		//位于左邊的一半|或者位于右邊的一半 
		int center = (left+right)/2;
		int leftsum = MaxSubsum(a,left,center); 
		int rightsum = MaxSubsum(a,center+1,right);
		
		//位于中間部分
		//先求左邊的最大值 
		int s1=0,lefts=Integer.MIN_VALUE;
		for(int i=center;i>=left;i--){
			s1+=a[i];
			if(lefts<s1){
				lefts = s1;
			}
		}
		//右邊最大值 
		int s2=0,rights=Integer.MIN_VALUE;
		for(int i=center+1;i<=right;i++){
			s2+=a[i];
			if(rights<s2){
				rights = s2;
			}
		}
		//求三者中的最大值
		sum = rights+lefts;
		if(sum<leftsum) sum=leftsum;
		if(sum<rightsum) sum = rightsum; 
	}
	return sum;
} 
}
           

動态規劃

class Solution {
    public int maxSubArray(int[] a) {
    int n = a.length;
    int []b = new int[n];
	b[0]=a[0];
    int max=b[0];
    for(int i=1; i<n; i++)
    {
        if(b[i-1]>0)
            b[i]=b[i-1]+a[i];
        else
            b[i]=a[i];
        if(b[i]>max)
            max=b[i];
    }
	return max;

    }
           

思路解析請參考我的部落格：算法學習（三）動态規劃（重要）