algorithm 탐욕 동적 프로그래밍:zig zag 인 가장 긴 하위 시퀀스 찾기




탐욕 알고리즘 동적 계획법 (9)

아무도 내가 http://www.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493 언급 된 문제에 대한 해결책 뒤에 숨어있는 핵심 논리를 이해하도록 도와 줄 수 있습니까?

지그재그 시퀀스는 번갈아 증가하거나 감소하는 시퀀스입니다. 그래서 1 3 2는 지그재그입니다. 그러나 1 2 3은 아닙니다. 하나 또는 두 개의 요소로 이루어진 모든 시퀀스는 지그재그입니다. 우리는 주어진 시퀀스에서 가장 긴 zig zag 서브 시퀀스를 찾아야합니다. 서브 시퀀스는 요소가 연속적으로 존재할 필요가 없다는 것을 의미합니다. 그래서 1 3 5 4 2는 1 5 4를 지그재그 서브 시퀀스로 가질 수 있습니다. 우리는 가장 긴 것에 흥미가 있습니다.

이것이 동적 프로그래밍 문제이며 동적 프로그래밍 을 사용하여 가장 길게 증가하는 서브 시퀀스를 결정하는 방법 과 매우 유사하다는 것을 알고 있습니다. .

모든 솔루션은 서로 다른 길이의 시퀀스를 반복하는 외부 루프가 필요하며 내부 루프는 모든 시퀀스를 반복해야한다고 생각합니다.

인덱스 i에서 끝나는 가장 긴 지그재그 시퀀스를 다른 배열, 즉 인덱스 i의 dpStore에 저장합니다. 따라서 중간 결과는 저장되고 나중에 다시 사용할 수 있습니다. 이 부분은 모든 동적 프로그래밍 문제에 공통적입니다. 나중에 우리는 전역 최대 값을 찾고 그것을 반환합니다.

내 솔루션은 분명히 틀렸어. 지금까지 내가 한 것을 보여주기 위해 붙여 넣기. 나는 내가 어디로 잘못되었는지 알고 싶다.

    private int isZigzag(int[] arr)
{
    int max=0;
    int maxLength=-100;
    int[] dpStore = new int[arr.length];

    dpStore[0]=1;

    if(arr.length==1)
    {
        return 1;
    }
    else if(arr.length==2)
    {
        return 2;
    }
    else 
    {           
        for(int i=3; i<arr.length;i++)
        {
            maxLength=-100;
            for(int j=1;j<i && j+1<=arr.length; j++)
            {
                if(( arr[j]>arr[j-1] && arr[j]>arr[j+1])
                    ||(arr[j]<arr[j-1] && arr[j]<arr[j+1]))
                {
                    maxLength = Math.max(dpStore[j]+1, maxLength);
                }
            }
            dpStore[i]=maxLength;               
        }
    }
    max=-1000;
    for(int i=0;i<arr.length;i++)
    {
        max=Math.max(dpStore[i],max);
    }
    return max; 
}

int zigzag (int [] a) {

List<Integer> list= new ArrayList<>();
int max = 0;
if(a.length==0 || a.length==1) return 0;
if(a.length==2) return 1;
for(int i=1;i<a.length-1;i++){

    if((a[i-1]<a[i] && a[i+1]<a[i]) || (a[i-1]>a[i] && a[i+1]>a[i])){
        if(list.isEmpty()){
           list.add(a[i-1]); 
        }
        list.add(a[i]);

    }else{
        list.add(a[i+1]); 
        max = Math.max(max,list.size());
        list.clear();
    }

}
return max;

}


def 지그재그 (tup) :

length = len(tup)
lst = []
lst.append(1)
lst.append(2)
if length > 2:
    for i in range(2,length):
        if (tup[i]-tup[i-1]) * (tup[i-1]-tup[i-2]) < 0:
            d = lst[i-1] + 1
        else:
            d = lst[i-1]
        lst.append(d)

return lst[length-1]

여기에 O (n)

public static int longestZigZag(int[] sequence) {
    if (sequence == null) {
        return 0;
    }

    int len  = sequence.length;
    if (len <= 2) {
        return len;
    }
    int minima = sequence[0];
    int maxima = sequence[0];
    int maximalen = 1;
    int minimalen = 1;

    for (int i = 1; i < len; i++) {
        if (sequence[i] < maxima) {
            if (minimalen < maximalen + 1) {
                minimalen = maximalen + 1;
                minima = sequence[i];
            } else if (minimalen == maximalen + 1 && sequence[i] < minima) {
                minima = sequence[i];
            }
        }
        if (sequence[i] > minima) {
            if (maximalen < minimalen + 1) {
                maximalen = minimalen + 1;
                maxima = sequence[i];
            } else if (maximalen == minimalen + 1 && sequence[i] > maxima) {
                maxima = sequence[i];
            }
        }
    }

    return Math.max(maximalen, minimalen);
}

실제로 나는 가장 높은 점수를 가진 대답이 정확하다고 생각합니다 (IVlad 's). 하지만 동적 프로그래밍 부분 (바깥 쪽 루프)이 필요 하지 않다는 것을 확신합니다.

욕심 많은 접근법이 사용되며 연산에 의해 positive_end_seq[i]negative_end_seq[i] 를 얻을 수 있습니다.

    positive_end_seq[i] = negative_end_seq[i-1];
    negative_end_seq[i] = positive_end_seq[i-1];
    if (A[i-1] > A[i]) { // next element for positive_end_seq
       positive_end_seq[i] += 1; 
    }
    if (A[i-1] < A[i]) { // next element for negqtive_end_seq
       negative_end_seq[i] += 1;
    }
    // if (A[i-1] == A[i]) values don't change

positive_end_seq[0] = 1negative_end_seq[0] = 1 , 모두 i 대한 두 배열 모두 i 번째 요소로 끝나는 pos / neg와 함께 가장 긴 하위 시퀀스의 길이를 포함합니다. 우리는 0..i-2 요소를 볼 필요가 없으며 그것을 증명하는 것이 좋을 것입니다.

시간 복잡도는 O(n)

물론 pos / neg 배열은 이제 카운터로 대체 될 수 있습니다. 여기에 Java 코드가 있습니다.

    public static int subZigZag(int[] arr) {
      int pos_count = 1;
      int neg_count = 1;
      for(int i = 1; i < arr.length; ++i) {
        if (arr[i-1] < arr[i]) {
          pos_count = neg_count + 1;
        }
        if (arr[i-1] > arr[i]) {
          neg_count = pos_count+1;
        }
      }
      return Math.max(pos_count, neg_count);
    } 

public static int longestZigZag(int[] sequence) {
    int max_seq = 0;

    if (sequence.length == 1) {
        return 1;
    }

    if (sequence.length == 1) {
        return 2;
    }

    int dp[] = new int[sequence.length];

    dp[0] = 1;
    dp[1] = 2;

    for (int i = 2; i < sequence.length; i++) {
        for (int j = i - 1; j > 0; j--) {
            if (((sequence[i] > sequence[j] &&
                sequence[j] < sequence[j - 1]) || 
                (sequence[i] < sequence[j] &&
                sequence[j] > sequence[j - 1])) &&
                dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;

                if (dp[i] > max_seq) {
                    max_seq = dp[i];
                }
            } 
        }
    }

    return max_seq;
}

또는 욕심 많은 알고리즘을 사용할 수 있습니다.

public static int longestZigZag(int[] sequence) {
    if (sequence.length==1) return 1;
    if (sequence.length==2) return 2;
    int[] diff = new int[sequence.length-1];

    for (int i=1;i<sequence.length;i++){
        diff[i-1]=sequence[i]-sequence[i-1];
    }
    int prevsign=sign(diff[0]);
    int count=0;
    if (prevsign!=0)
        count=1;
    for (int i=1;i<diff.length;i++){
        int sign=sign(diff[i]);
        if (prevsign*sign==-1){
            prevsign=sign;
            count++;
        }
    }
    return count+1;
}

public static int sign(int a){
    if (a==0) return 0;
    return a/Math.abs(a);
}

이것은 더 간단한 해결책입니다.

원래 배열 A의 길이가 n이라고합시다. 단지 0과 1의 길이 n-1의 다른 배열 B를 만듭니다. [i] -a [i + 1]> 0이면 B [i] = 0 그렇지 않으면 B [i] = 1입니다. 이것은 O (n)에서 수행 할 수 있습니다. 이제 우리는 단지 0과 1의 배열을 가지므로, 문제는 연속적인 0과 1을 교대로 찾는 것입니다. 0의 B에있는 연속적인 하위 배열 배열은 그 요소 중 하나에 의해 표현됩니다. 예를 들어, B가 = [0,0,0,0,0, 1,0,0,0,1,0,1,1,1,0]이면 B를 Br로 줄이면됩니다. = [0, 1,0,1,0,1,0] O (n)에서, 실제로 우리는 단지 하나의 반복으로 수행 할 수있는 Br의 크기를 찾아야합니다. 그리고 내 친구는 주어진 문제에 대한 답입니다. 따라서 총 복잡도는 O (n) + O (n) = O (n)입니다. 즉, 첫 번째 요소를 유지하십시오. 그런 다음 시퀀스의 부분을 늘리거나 줄이는 모노톤을 찾고 이러한 모든 시퀀스의 마지막 요소를 유지합니다.

업데이트 : 목록의 길이가 아닌 지그재그를 계산하기 때문에이 과정에서 나오는 대답에 하나를 추가해야합니다. 담장 게시 문제에주의하십시오. https://betterexplained.com/articles/learning-how-to-count-avoiding-the-fencepost-problem/


이것은 간단한 욕심 많은 구현에 대한 나의 생각이다.

다른 사람들이 이전에 언급 한 것처럼, 마지막 세 가지 점을보아야합니다.

def zigzag(xs):
    res = xs[:2]
    for x in xs[2:]:
        if cmp(res[-1], x) == cmp(res[-1], res[-2]):
            res.append(x)
        else:
            res[-1] = x
    return res

로컬 최대 값과 로컬 최소 값을 선택하십시오. 아주 간단합니다.

vector<int> longest_oscilating_subsequence(const vector<int> seq) {
    vector<int> result; // the resulting subsequence 

    for (int i = 0; i < seq.size(); ++i) {
        if (i > 0 && seq[i] == seq[i - 1]) continue;

        // is this point a local extreme 
        bool local_max = true, local_min = true;
        if (i > 0) {
            local_max = local_max && (seq[i] >= seq[i - 1]);
            local_min = local_min && (seq[i] <= seq[i - 1]);
        }
        if (i < seq.size() - 1) {
            local_max = local_max && (seq[i] >= seq[i + 1]);
            local_min = local_min && (seq[i] <= seq[i + 1]);
        }

        // potentially add it to the sequence 
        if (local_max || local_min) result.push_back(seq[i]);
    }

    return result; 
}




dynamic-programming