leetcode-53-最大サブシーケンスおよび(maximum subarray)-java

タイトルと使用例

package pid053;
/*     

         nums ，               （           ），      。

  :

  : [-2,1,-3,4,-1,2,1,-5,4],
  : 6
  :       [4,-1,2,1]     ，  6。

  :

            O(n)    ，              。
*/




public class main {
	
	public static void main(String[] args) {
		int[][] testTable = {{-2,1,-3,4,-1,2,1,-5,4},{-1,-2,-3,-4,-1},{7,-6,4,3,1},{-1,6,2,7}};
		for (int[] ito : testTable) {
			test(ito);
		}
	}
		 
	private static void test(int[] ito) {
		Solution solution = new Solution();
		int rtn;
		long begin = System.currentTimeMillis();
		for (int i = 0; i < ito.length; i++) {
		    System.out.print(ito[i]+" ");		    
		}
		System.out.println();
		//       
		
		rtn = solution.maxSubArray(ito);//    
		long end = System.currentTimeMillis();	
		
		//System.out.println(ito + ": rtn=" + rtn);
		System.out.println( " rtn=" +rtn);
//		for (int i = 0; i < ito.length; i++) {
//		    System.out.print(ito[i]+" ");
//		}//       
		
		System.out.println();
		System.out.println("  ：" + (end - begin) + "ms");
		System.out.println("-------------------");
	}

}

解法1(成功,16 ms,比較的速い)速度o(n)法は累積し続けることであり,現在の値を負数に加算し,max値を更新してから負数を加算し,0未満であれば0に初期化し,最後のmaxが0であればすべて負数であることを証明するにかかわらず負数の中で最大の数をとる

package pid053;


class Solution {
public int maxSubArray(int[] nums) {
    int length=nums.length;
    if(length==0){
    	return 0;
    }
    int totalMax=0;
    int nowMax=0;
    for(int i=0;i=0){
    			nowMax=now;
    			continue;
    		}
    		else {
				continue;
			}
    		
    	}
    	else {//       
			if(now>=0){
				nowMax=nowMax+now;
				continue;
			}
			else{//               
				
				if(nowMax>totalMax){//        ，   max 
					totalMax=nowMax;
				}				
				nowMax=nowMax+now;
				if(nowMax<0){
					nowMax=0;
				}
				continue;
			}
    		
		}
    	
    }
	
    if(nowMax>totalMax){
		totalMax=nowMax;
	}
    if(totalMax==0){//      
    	totalMax=nums[0];
    	for(int i=0;itotalMax){
    			totalMax=now;
    		}
    	}
    }
	
	return totalMax;
    }
}

解法2(成功,3 ms,遅い)dpアルゴリズムiにおけるmax利益max[i]=max[i]=max[i-1]/tail[i-1]+nums[i]/nums[i]iを含むmax利益tail[i]=tail[i-1]+nums[i]/nums[i]は、毎回前の変数のみが必要となるため、4つの変数を設定するだけでよい

    public int maxSubArray(int[] nums) {
        // i  max    max[i]  =  max[i-1]/tail[i-1]+nums[i]/nums[i]
    	//   i max     tail[i] = tail[i-1]+nums[i] / nums[i] 
    	int prevMax=nums[0];
    	int prevTail=nums[0];
    	int max=nums[0];
    	int tail=nums[0];
    	for(int i=1;i

解法3ダイナミックプランニングという問題はダイナミックプランニングの考え方では難しくなく,後で提案した分治法で解くのが難しいが,最適解法ではないため,まずダイナミックプランニングを列挙しないのはまず配列を遍歴し,現在の最大連続サブシーケンスとsumであり,結果はansでsum>0であればsumが結果に利得効果があることを説明する.sumは現在の遍歴数を保持し、加えてsum<=0の場合、sumは結果に対して利得効果がなく、捨てる必要があることを示します.sumは現在の遍歴数に直接更新され、sumとansの大きさを比較するたびに最大値をansに設定します.遍歴終了の戻り結果は、私の上の解法2と同様に、ansはiの最大利益です.sumはiにおける最大理論iにおけるmax利益max[i]=max[i]=max[i-1]/tail[i-1]+nums[i]/nums[i]を含むmax利益tail[i]=tail[i-1]+nums[i]/nums[i]がtail[i]=tail[i-1]+nums[i]/nums[i]max[i]=max[i-1]/tail[i]になると元の式が見え、裏面の2つの値がtail[i]の値となり、これに置き換えることで2つの変数だけで済み、計算を繰り返す必要はありません

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for(int num: nums) {
            if(sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

解法4(他人の)分治法:構想:配列下標有効範囲がlからrであると仮定し、配列を左半分下標(l,mid-1)と右半分下標(mid+1,r)と中間要素下標midに分け、次に左半分の最大サブシーケンス和を再帰的に求める:left=helper(nums,l,mid-1);右半分の最大サブシーケンスとright=helper(nums,mid+1,r);次に、左半分の右境界、右半分の左境界、および中間要素nums[mid]を統合し、2つのサイクルを使用して、左半分の右境界と中間値を統合し、統合結果を右半分の左境界と統合した後の最大サブシーケンスとmax_num、最後にmax_を返しますnum,left,rightの最大値は,要求される最大サブシーケンス和である.

class Solution {
public:
    int maxSubArray(vector& nums) {
        if(nums.size()==0)return 0;
        return helper(nums,0,nums.size()-1);
    }
    int helper(vector& nums,int l,int r){
        if(l>r)return INT_MIN;//        0，  ｛-2，-1｝，         n｛｝，-1，｛-2｝   。    ｛｝   INT_MIN，
        //                 ,        -1。       0，0>-2,            （-1），      0，  
        if(l==r)return nums[l];
        int mid=(l+r)/2;
        int left=helper(nums,l,mid-1);
        int right=helper(nums,mid+1,r);
        int t=nums[mid];
        int max_num=nums[mid];
        for(int i=mid-1;i>=l;i--){
            t+=nums[i];
            max_num=max(max_num,t);
        }
        t=max_num;
        for(int i=mid+1;i<=r;i++){
            t+=nums[i];
            max_num=max(max_num,t);
        }
        return max(max(left,right),max_num);
    }
};