当前位置： 文江博客话题详情

动态规划：找到锯齿状的最长子序列

发布于 2024-11-27 16:09:04 字数 1688 浏览 1 评论 0原文

任何人都可以帮助我理解 http://www.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493 之

字形序列是交替增加和减少的一种。因此，1 3 2 是锯齿形，但 1 2 3 不是。任何一个或两个元素的序列都是锯齿形的。我们需要找到给定序列中最长的锯齿形子序列。子序列意味着元素不必是连续的，就像最长递增子序列问题一样。因此，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; 
}
原文

Can anyone please help me understand the core logic behind the solution to a problem mentioned at http://www.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493

A zig zag sequence is one that alternately increases and decreases. So, 1 3 2 is zig zag, but 1 2 3 is not. Any sequence of one or two elements is zig zag. We need to find the longest zig zag subsequence in a given sequence. Subsequence means that it is not necessary for elements to be contiguous, like in the longest increasing subsequence problem. So, 1 3 5 4 2 could have 1 5 4 as a zig zag subsequence. We are interested in the longest one.

I understand that this is a dynamic programming problem and it is very similar to How to determine the longest increasing subsequence using dynamic programming?.

I think any solution will need an outer loop that iterates over sequences of different lengths, and the inner loop will have to iterate over all sequences.

We will store the longest zig zag sequence ending at index i in another array, say dpStore at index i. So, intermediate results are stored, and can later be reused. This part is common to all Dynamic programming problems. Later we find the global maximum and return it.

My solution is definitely wrong, pasting here to show what I've so far. I want to know where I went wrong.

    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; 
}

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（11）

花心好男孩 2024-12-04 16:09:05

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;

}

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;

}

回复 原文
夜清冷一曲。 2024-12-04 16:09:05

def ZigZag(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]

def ZigZag(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]
回复 原文
厌味 2024-12-04 16:09:05

选择局部最大值和局部最小值，非常简单。

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; 
}

Pick local maxima and local minima, very simple.

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; 
}
回复 原文
倒数 2024-12-04 16:09:04

这就是您链接到的问题所说的：

如果连续数字之间的差严格在正负之间交替，则数字序列称为锯齿序列。第一个差异（如果存在）可以是正值，也可以是负值。元素少于两个的序列通常是锯齿形序列。

例如，1,7,4,9,2,5 是锯齿序列，因为差值 (6,-3,5,-7,3) 交替正负。相反，1,4,7,2,5 和 1,7,4,5,5 不是锯齿序列，第一个是因为它的前两个差值为正，第二个是因为它的最后一个差值为零。

给定一个整数序列，序列，返回序列的最长子序列的长度，该序列是锯齿序列。子序列是通过从原始序列中删除一些元素（可能为零）而获得的，而其余元素仍保持其原始顺序。

这与您在帖子中描述的完全不同。下面解决实际的topcoder问题。

dp[i, 0] = maximum length subsequence ending at i such that the difference between the
           last two elements is positive
dp[i, 1] = same, but difference between the last two is negative

for i = 0 to n do     
   dp[i, 0] = dp[i, 1] = 1

   for j = 0 to to i - 1 do
    if a[i] - a[j] > 0
      dp[i, 0] = max(dp[j, 1] + 1, dp[i, 0])
    else if a[i] - a[j] < 0
      dp[i, 1] = max(dp[j, 0] + 1, dp[i, 1])

示例：

i        = 0  1   2  3   4   5   6   7  8   9
a        = 1  17  5  10  13  15  10  5  16  8 
dp[i, 0] = 1  2   2  4   4   4   4   2  6   6    
dp[i, 1] = 1  1   3  3   3   3   5   5  3   7
           ^  ^   ^  ^
           |  |   |  -- gives us the sequence {1, 17, 5, 10}
           |  |   -- dp[2, 1] = dp[1, 0] + 1 because 5 - 17 < 0.
           |  ---- dp[1, 0] = max(dp[0, 1] + 1, 1) = 2 because 17 - 1 > 0
     1 element
   nothing to do
 the subsequence giving 7 is 1, 17, 5, 10, 5, 16, 8, hope I didn't make any careless
 mistakes in computing the other values)

然后取两个 dp 数组的最大值。

This is what the problem you linked to says:

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

This is completely different from what you described in your post. The following solves the actual topcoder problem.

dp[i, 0] = maximum length subsequence ending at i such that the difference between the
           last two elements is positive
dp[i, 1] = same, but difference between the last two is negative

for i = 0 to n do     
   dp[i, 0] = dp[i, 1] = 1

   for j = 0 to to i - 1 do
    if a[i] - a[j] > 0
      dp[i, 0] = max(dp[j, 1] + 1, dp[i, 0])
    else if a[i] - a[j] < 0
      dp[i, 1] = max(dp[j, 0] + 1, dp[i, 1])

Example:

i        = 0  1   2  3   4   5   6   7  8   9
a        = 1  17  5  10  13  15  10  5  16  8 
dp[i, 0] = 1  2   2  4   4   4   4   2  6   6    
dp[i, 1] = 1  1   3  3   3   3   5   5  3   7
           ^  ^   ^  ^
           |  |   |  -- gives us the sequence {1, 17, 5, 10}
           |  |   -- dp[2, 1] = dp[1, 0] + 1 because 5 - 17 < 0.
           |  ---- dp[1, 0] = max(dp[0, 1] + 1, 1) = 2 because 17 - 1 > 0
     1 element
   nothing to do
 the subsequence giving 7 is 1, 17, 5, 10, 5, 16, 8, hope I didn't make any careless
 mistakes in computing the other values)

Then just take the max of both dp arrays.

回复 原文
落墨 2024-12-04 16:09:04

这是一个更简单的解决方案

让原始数组 A 的长度为 n。构建另一个长度为 n-1 且仅包含 0 和 1 的数组 B。如果a[i]-a[i+1]>=0，则B[i]=0，否则B[i]=1。这可以在O(n)内完成。现在我们有一个只有 0 和 1 的数组，现在的问题是找到交替的连续 0 和 1。 B of 0 中的连续子数组数组将由其任意一个元素表示。例如：
如果 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/

This is a simpler solution

Let the original array A be of length n. Build another array B of length n-1 of only 0s and 1s. B[i] = 0 if a[i]-a[i+1] >=0 else B[i] = 1. This can be done in O(n). Now we have an array of only 0s and 1, now the problem is to find alternating continuous 0s and 1s. A continuous sub array array in B of 0s will be represented by any one of its elements. For example:
If B is = [0,0,0,0,0, 1,0,0,0,1,0,1,1,1,0] then we can reduce B to Br which = [0,1,0,1,0,1,0] in O(n), in fact we just need to find the size of Br which can be done by just one iteration. And that my friend is the answer to the given problem. So total complexity is O(n) + O(n) = O(n).
In other words:
Keep the first element. Then find the monotone growing or shrinking parts of the sequence and keep the last element from all of these sequences.

UPDATE: You need to add one to the answer coming out of this process, because you are counting the zigzags, not the length of the list. Beware of the fence post problem: https://betterexplained.com/articles/learning-how-to-count-avoiding-the-fencepost-problem/

回复 原文
脱离于你 2024-12-04 16:09:04

还有一种贪婪的方法。

取第一个元素。然后找出包含第一个元素的连续序列中的最小或最大元素并选择它。

也就是说，如果序列是 1, 5, 7, 9, 2,4，首先选择 1，然后选择 9，因为 9 是连续序列 1, 5, 7, 9..

以同样的方式进行，选择2和5。
使用相同的方法，为示例计算的子序列

1, 17, 5, 10, 13, 15, 10, 5, 16, 8

为：1, 17, 5, 15, 5, 16, 8

There is a greedy approach also.

Take the first element. Then find out the minimum or maximum element in the contiguous sequence including the first element and select it.

That is if the sequence is 1, 5, 7, 9, 2,4, first select 1, and then 9 because 9 is the maximum in the contiguous sequence 1, 5, 7, 9.

Proceed in the same manner and select 2 and 5.
Using same approach, the subsequence computed for the example:

1, 17, 5, 10, 13, 15, 10, 5, 16, 8

is: 1, 17, 5, 15, 5, 16, 8

回复 原文
命硬 2024-12-04 16:09:04

或者你可以使用贪心算法

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);
}

or you can use greedy algorithm

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);
}
回复 原文
温馨耳语 2024-12-04 16:09:04

实际上我认为得分最高的答案是正确的（IVlad）。但我很确定动态编程部分（外循环）是不需要的。

使用贪心方法，我们可以通过操作：

    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] = 1 和 < code>negative_end_seq[0] = 1，所有 i 的两个数组都包含以 pos/neg 结尾的最长子序列的长度第 i 个元素。我们不必查看 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);
    }

Actually I think that answer with highest score is correct (IVlad's). But I'm pretty sure that the dynamic programming part (outer loop) is not necessary.

A greedy approach is used and we can obtain positive_end_seq[i] and negative_end_seq[i] by operations:

    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] = 1 and negative_end_seq[0] = 1, both arrays for all i's contain length of the longest subsequence with pos/neg ending in i-th element. We don't have to look at 0..i-2 elements, and it would be nice to prove that.

Time complexity is O(n)

Of course, pos/neg array can be replaced by counters now, here is code in 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);
    }
回复 原文
树深时见影 2024-12-04 16:09:04
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) {
    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;
}
回复 原文
匿名。 2024-12-04 16:09:04

这是我对简单贪婪实现的看法。

就像其他人之前提到的那样，您只需要查看最后三个点的曲折即可。

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

This is my take on a simple greedy implementation.

Like others have previously mentioned, you simply need to look at the zag'ing of the three last points.

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
回复 原文
镜花水月 2024-12-04 16:09:04

这是如何在 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);
}

Here is how did it in 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);
}
回复 原文
~没有更多了~

关于作者

疏忽

暂无简介

0 文章
0 评论
24 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

胡图图

文章 0 评论 0

zt006

文章 0 评论 0

z祗昰~

文章 0 评论 0

冰葑

文章 0 评论 0

野の

文章 0 评论 0

天空

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文