leetccode 53. 最大サブシーケンスおよび152.積最大サブシーケンスjava(局所最適化とグローバル最適化解法)

leetccode 53. 最大サブシーケンスおよび152.積最大サブシーケンスjava(局所最適化とグローバル最適化解法)
整数配列numsを指定し、最大和を持つ連続サブ配列(サブ配列には少なくとも1つの要素が含まれている)を見つけ、その最大和を返します.

  :

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

  :

            O(n)    ，              。

「局所最適化とグローバル最適化の解法」:基本的な考え方は、ステップごとに、2つの変数を維持し、1つはグローバル最適化であり、現在の要素までの最適化の解であり、1つは局所最適化であり、現在の要素を含まなければならない最適化の解である.次に、動的計画の繰返し式について述べる.(これはダイナミックプランニングの最も重要なステップであり,再帰式が出てきて,基本的にコードフレームワークも出てきた).iステップ目のglobal[i](グローバル最適)とlocal[i](ローカル最適)が既知であると仮定すると、i+1ステップ目の式は、local[i+1]=Mathである.max(A[i],local[i]+A[i])は、局所最適化は必ず現在の要素を含むので、そうでなければ前のステップの局所最適local[i]+現在の要素A[i](local[i]は必ずi番目の要素を含むので、条件に違反しません)ですが、local[i]が負であれば、彼を加えるより不要なので、そうでなければ直接A[i]を使います.global[i+1]=Math(local[i+1],global[i])は、現在のステップのローカル最適化があり、グローバル最適化は、現在のローカル最適化または元のグローバル最適化である(最適解が現在の要素を含まない場合、前はグローバル最適化の中に維持され、現在の要素が含まれている場合、このローカル最適化であるため、すべての状況がカバーされる).
次に複雑度を解析すると,時間的に配列を1回スキャンするだけなので,時間複雑度はO(n)である.空間的には、式では前のステップlocal[i]とglobal[i]だけで次のステップの結果が得られることが分かるので、実装ではこの結果を1つの変数で反復することができ、1つの配列、すなわちプログラムで実装されるように、空間複雑度は2つの変数(localとglobal)、すなわちO(2)=O(1)である.

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        //         
        int local = nums[0];
        int global = nums[0];
        
        for(int i = 1; i < nums.length; i ++){
            local = Math.max(nums[i], local+nums[i]);
            global = Math.max(local, global);
        }
        return global;

    }
}

整数配列numsが与えられ、少なくとも1つの数を含むシーケンスの積が最も大きい連続サブシーケンスが見出される.

   1:

  : [2,3,-2,4]
  : 6
  :     [2,3]       6。
   2:

  : [-2,0,-1]
  : 0
  :       2,    [-2,-1]      。

class Solution {
    public int maxProduct(int[] nums) {
        int[] maxdp = new int[nums.length];
        int[] mindp = new int[nums.length];
        maxdp[0] = mindp[0] = nums[0];
        
        for(int i = 1; i < nums.length; i++){
            if(nums[i] >= 0){
                maxdp[i] = Math.max(maxdp[i - 1] * nums[i], nums[i]);
                mindp[i] = Math.min(mindp[i - 1] * nums[i], nums[i]);
            }else{
                maxdp[i] = Math.max(mindp[i - 1] * nums[i], nums[i]);
                mindp[i] = Math.min(maxdp[i - 1] * nums[i], nums[i]);
            }
        }
        int result = Integer.MIN_VALUE;
        for(int i = 0; i < maxdp.length ; i++){
            if(maxdp[i] > result){
                result = maxdp[i];
            }
        }
        return result;
    }
}

class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int max = nums[0], min = nums[0], result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int temp = max;
            max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
            min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]);
            if (max > result) {
                result = max;
            }
        }
        return result;
    }
}