3

输入： n ( int) 和n值 ( float)，表示汇率（它们之间不同），随机值介于4和之间5。

输出：计算可用于（以相同顺序）表示先升后降曲线的值的最大数量？

ex 八个值

4.5 4.6 4.3 4.0 4.8 4.4 4.7 4.1

应该输出

5 (4.5 4.6 4.8 4.4 4.1)

我的方法

  • 如果我尝试连续if的 s，我会得到一个尊重曲线条件的随机数组，但不是最长的。
  • 我没有尝试回溯，因为我对它不是很熟悉，但有些事情告诉我，我必须用它计算所有解决方案，然后选择最长的。
  • 最后：蛮力，但因为它是算法设计的任务；我还不如不交。:)

有没有更简单/更有效/更快的方法？

这是我基于 Daniel Lemire 算法的尝试。似乎它没有考虑位置 0、i 和 n。我确定ifs是问题所在，我该如何解决它们？

for(int i = 0; i<n-1; i++){
            int countp=0;   // count ascending
            int countn=0;   // count descending
            for(int j=0;j<=i;j++){
                    if(currency[j]<currency[j+1]){
                        countp++;
                        System.out.print(j+" ");
                    }
                }
            System.out.print("|| ");
            for(int j=i;j<n-1;j++){
                if(currency[j]>currency[j+1]){
                    countn++;
                    System.out.print(j+" ");
                }
            }
        System.out.println();
        if(countn+countp>maxcount) maxcount=countn+countp;                   
        }
4

2 回答 2

3

首先，您希望能够计算从一个点到另一个点的最长单调子序列。（增加或减少对问题的影响不大。）为此，您可以使用动态规划。例如，要解决给定索引 0 到 i 的问题，首先从 0 到 0（微不足道！）解决问题，然后从 0 到 1，然后从 0 到 2，依此类推，每次记录（在阵列）您的最佳解决方案。

例如，下面是 python 中的一些代码，用于计算从索引 0 到索引 i 的最长非递减序列。我们使用一个数组（bbest）来存储从 0 到 i 的所有 j 的从 0 到 j 的解：即从 0 到 j 的最长非递减子序列的长度。（使用的策略是动态规划。）

def countasc(array,i):
  mmin = array[0] # must start with mmin
  mmax= array[i] # must end with mmax
  bbest=[1] # going from 0 to 0 the best we can do is length 1
  for j in range(1,i+1): # j goes from 1 to i
    if(array[j]>mmax):
      bbest.append(0) # can't be used
      continue
    best = 0 # store best result
    for k in range(j-1,-1,-1): # count backward from j-1 to 0
      if(array[k]>array[j]) :
        continue # can't be used
      if(bbest[k]+1>best):
          best = bbest[k]+1
    bbest.append(best)
  return bbest[-1] # return last value of array bbest

或等效地在 Java 中（由请求提供）：

int countasc(float[] array,int i) {
    float mmin = array[0];
    float mmax = array[i];
    ArrayList<Integer> bbest= new ArrayList<Integer>();
    bbest.add(1);
    for (int j = 1; j<=i;++j) {
        if(array[j]>mmax){
            bbest.add(0);
            continue;
        }
        int best = 0;
        for(int k = j-1; k>=0;--k) {
            if(array[k]>array[j]) 
                continue;
            if(bbest.get(k).intValue()+1>best)
                best = bbest.get(k).intValue()+1;
        }
        bbest.add(best);
    }
    return bbest.get(bbest.size()-1);
}

您可以编写相同类型的函数来找到从 i 到 n-1 的最长非递增序列（作为练习留下）。

请注意，countasc 以线性时间运行。

现在，我们可以解决实际问题：

Start with S, an empty array
For i an index that goes from 0 to n-1 :
  compute the length of the longest increasing subsequence from 0 to i (see function countasc above)
  compute the length of the longest decreasing subsequence from n-1 to i
  add these two numbers, add the sum to S
return the max of S

它具有二次复杂度。我相信你可以改进这个解决方案。这种方法有很多冗余。例如，为了速度，您可能不应该用未初始化的数组 bbest 重复调用 countasc：它可以计算一次。可能您可以通过更多工作将复杂性降低到 O(n log n)。

于 2011-12-02T02:37:38.127 回答
1

第一步是了解如何解决相关的最长递增子序列问题。对于这个问题，有一个简单的算法，O(n^2)虽然最优算法是O(n log n)。了解这些算法应该会让您走上解决方案的正确轨道。

于 2011-12-02T02:08:11.417 回答