2

该程序的要点是使用蛮力方法（有效！）和分治法（无效）找到具有波动股票价格的一维数组的最大子数组。该程序的目的是找到天的集合（因此结构中的 lsub 和 rsub）和这些天的最大利润。

我在网上看到的所有地方，比如这个 powerpoint都表明我的代码应该可以工作。我也看到了类似的东西，但是在 StackOverflow 上的 Java 中，该代码的实现也不起作用。这是该 Java 程序的链接。

我的代码如下：

#include <stdio.h>
#include <iostream>
#include <climits>
#include <cstring>

struct funOut{
int lsub; //Left subscript
int rsub; //Right subscript
int maximum; //Contains the max value
 //This way, max has the absolute smallest value and only needs to be done once rather than at the beginning of the algorithm calls.
};

void load(int arr[], int n);
void brute(int arr[],  int n, funOut &out);
funOut dac(int arr[], int low, int high, funOut &out);
void findMax(int sumLval, int sumRval, funOut &sumMval, int low, int mid, int high, funOut &out);
funOut crossSum(int arr[], int low, int mid, int high);
void print(funOut out);

using namespace std;


int main(void)
{
   funOut out;

   string alg;
   cin >> alg;

   int n;
   cin >> n;

   int arr[n];

   // cout << n << endl;

   load(arr, n);
   if(alg[0] == 'b')
      brute(arr, n, out); //PARAMETERS NEEDED
   else if(alg[0] == 'd')
   {
      out.maximum = 0;
      out = dac(arr, 1, n-1, out);
   }

   else
   {
      cout << "\nERROR: No algorithm chosen, aborting program." << endl;
      return 0;
   }

   cout << "Before Print" << endl;
   print(out);
   return 0;
}

void load(int arr[], int n)
{
   cout << "Loading" << endl;
   for(int i=0; i<n; i++)
      cin >> arr[i];
}

void brute(int arr[], int n, funOut &out) //THIS WORKS!!!
{
   out.maximum = 0;
   int change;
   int temp = 0;
   for(int i=1; i<n-1; i++)
   {
      for(int j=i; j<n; j++)
      {
         change = arr[j] - arr[j-1];
         temp += change;
         if(temp > out.maximum){
            out.lsub = i;
            out.rsub = j;
            out.maximum = temp;
         }     
      }
      temp = 0;
   }
}

funOut dac(int arr[], int low, int high, funOut &out)
{
   cout << "DAC Start!" << endl;
   if(low == high)
   {
      out.lsub = out.rsub = low;
      out.maximum = arr[low];
      return out;
   }
   else
   {
      // cout << "DAC IF" << endl;
      int mid = (low + high)/2;

      funOut sumLval = dac(arr, low, mid, out);
      funOut sumRval = dac(arr, mid+1,high, out);
      funOut sumMval = crossSum(arr, low, mid, high);

      cout << "\nsumLval = " << sumLval.maximum << endl; 
      cout << "\nsumRval = " << sumRval.maximum << endl;
      cout << "\nsumMval = " << sumMval.maximum << endl;
      //FindMax
      if(sumLval.maximum >= sumRval.maximum && sumLval.maximum >= sumMval.maximum)
         return sumLval;         
      else if(sumRval.maximum >= sumLval.maximum && sumRval.maximum >= sumMval.maximum)
         return sumRval;
      else
         return sumMval;
   }
}



funOut crossSum(int arr[], int low, int mid, int high)
{
funOut sumMval;
int lsum = 0;
int rsum = 0;
int sum = 0;
int maxl, maxr;
//For loop finding lsum
for(int i=mid; i>=low; i--)
{
   cout << "DAC For I = " << i << endl;
   sum += arr[i];
   if(sum > lsum)
   {
      lsum = sum;
      maxl = i;
   }
}

sum = 0;

for(int j=mid+1; j<=high; j++)
{
   cout << "DAC For J = "<< j << endl;
   sum += arr[j];
   if(sum > rsum)
   {
      rsum = sum;
      maxr = j;
   }
}

sumMval.lsub = maxl;
sumMval.rsub = maxr;
sumMval.maximum = lsum + rsum;

return sumMval;
}

void print(funOut out)
{
   cout << "The max value is: ";
   cout << out.maximum << endl;
   cout << "The left subscript is: ";
   cout << out.lsub << endl;
   cout << "The right subscript is: ";
   cout << out.rsub << endl;
}

示例数据集：（它们应该在单独的行上，但它不允许我这样做。）

d
17
100
113
110
85
105
102
86
63
81
101
94
106
101
79
94
90
97

预期的输出是：

最大值为：43

左下标为：8

右下标是：11

4

1 回答 1

0

从概念上讲，您的蛮力方法正在做大量多余的工作。

当您将数组中的所有点对点差异相加时，您得到的只是两端之间的差异：

int diff = (x[1] - x[0]) + (x[2] - x[1]) + (x[3] - x[2]) + (x[4] - x[3]);

以上与此相同（因为所有其他值都取消了）：

int diff = x[4] - x[0];

所以你所有的蛮力算法似乎正在做的是搜索i和j最大的差异受i < j. 这相当于找到数组的最小值和最大值，其中最小值出现在最大值之前。

在我看来，这像是动态编程的问题。我看不出分而治之对这个问题有什么用处。

[编辑]

所以，我认为问题是crossSum。它正在做一些与brute. 当然，您只想找到左侧 ( minl) 中的最小值的索引和右侧 ( ) 中的最大值的索引maxr。该输出结构中的“最大值”只是arr[maxr] - arr[minl].

有趣的是，对于这个问题，分而治之的方法仍然不必要地低效。考虑一下：

struct funOut f;
f.lsub = 0;
f.rsub = 0;
f.maximum = 0;

int minval = arr[0];
int minidx = 0;

for( int i = 1; i < n; i++ ) {
    if( arr[i] < minval ) {
        minval = arr[i];
        minidx = i;
        continue;
    }

    int delta = arr[i] - minval;
    if( delta > f.maximum ) {
        f.lsub = minidx;
        f.rsub = i;
        f.maximum = delta;
    }
}
于 2012-09-16T23:21:49.650 回答