[Algorithm Champions] Week 4, No.3

9103 ワード
アルゴリズム#アルゴリズム# DP テキストリンク

質問する



に答える


  • これは隣接しない数値を加算した最大値を返す問題です.

  • 点火式を確立し,dpで問題を解く.

  • arrayの上部を回って確認します.
  • から現在のインデックスの数字を比較し、加算できる最大値を新しい配列に入れます.
  • のように入力された値を比較すると、すぐに前の値が大きいか、2つの前の値に現在の値が大きいかを比較し、新しい配列の現在のインデックスに大きな値を入れます.
  • の新しい配列の最後の値を返すと、最大値が得られます.
  • 例)
    新しいシナリオb
    b[0]=75(最大値のため)
    b[1]=max(a[0],a[1])=105(2つの値のうち1つしか選択できない大きな値)
    b[2]=max(b[0]+a[2],b[1])=195(すなわち、前の値(b[1])が大きく、前の2つの値に現在の値(b[0]+a[2])を加え、後の値を比較すると大きくなり、現在195を値に加算する.)
    ...
    (上記のように)

    • コード#コード#

    package com.company.w4;

/*
date: 21.07.07  21:03 ~ 21:47

input: int array
output: int
constraints: input val - positive integer
  인접하지 않은 원소들을 더한 최대 값을 반환
edge cases:
  array is empty -> return 0
  array.length == 1 -> return array[0]

Brute force
data structure: array
algorithm: traversal

[75, 105, 120, 75, 90, 135]
for문 2번 돌기
sum1 = 75 + max(120,75) -> 120 + max(90, 135) -> 135 = 75 + 120 + 135 = 330
sum2 = 105 + max(75,90) -> 90
       105 + 75 + 135

맨 뒤 a[5] 선택될 경우 -> a[4]=90 x, max(120,75)
     a[4]           -> a[3]=75 x, max(105, 120)
 0 ~ 5
 // 본인 포함
 b[0] = 75
 b[1]= 105
 b[2]=b[0]+ a[2] = 195
 b[3]=b[1]+a[3] = 180
 b[4]=b[2]+a[4] = 285
 b[5]=b[3]+a[5] = 315

 // 본인 미포함
 b[0] = a[0] = 75
 b[1] = max(a[0],[a1]) = 105
 b[2] = max(b[0] + a[2], b[1]) = 195
 b[3] = max(b[1] + a[3], b[2]) = 105 + 75  < 195 = 195
 b[4] = max(b[2] + a[4], b[3]) = 195 + 90 > 195 = 285
 b[5] = max(b[3] + a[5], b[4]) = 195 + 135 > 285 = 330


 */

// time: O(N), space: O(N)
public class No3 {
    public static void main(String[] args) {
        int[] array = {75, 105, 120, 75, 90, 135};
        System.out.println(maxSubsetSum(array));
    }

    public static int maxSubsetSum(int[] array) {
        // base case
        if (array.length == 0) return 0;
        if (array.length == 1) return array[0];

        int[] maxArray = new int[array.length];

        maxArray[0] = array[0];
        maxArray[1] = Math.max(array[0], array[1]);

        for (int i = 2; i < maxArray.length; i++) {
            if (maxArray[i - 2] + array[i] > maxArray[i - 1]) {
                maxArray[i] = maxArray[i - 2] + array[i];
            } else {
                maxArray[i] = maxArray[i - 1];
            }
        }

        return maxArray[maxArray.length - 1];
    }
}
    mongodb操作増削除
    IM 69 1日目