7

给定一个整数数组...

var numbers = new int[] { 1,2,1,2,1,2,1,2,1,2,1,2,1,2,2,2,1,2,1 };

我需要确定一个上下交替或上下交替的最大数字序列。

不确定解决这个问题的最佳方法，这个过程 psuedo 明智地让我觉得很简单，但它的具体化代码正在逃避我。

关键是我们正在寻找最大序列这一事实，因此虽然上述数字可以用多种方式解释，例如七个上下上下和七个上下上下的序列，但重要的事实是从第一个数字开始有一个 14 长的 down-up-down 序列。

另外我不应该计算第一项，121 是一个长度为 3 的序列，有人可能会争辩说该序列直到第二个数字才开始，但不要分裂头发。

4

6 回答 6

3

这似乎可行，它假设数字的长度大于 4（无论如何，这种情况应该是微不足道的）：

var numbers = new int[] { 1,2,1,2,1,2,1,2,1,2,1,2,1,2,2,2,1,2,1 };
int count = 2, max = 0;
for (int i = 1; i < numbers.Length - 1; i++)
{

    if ((numbers[i - 1] < numbers[i] && numbers[i + 1] < numbers[i]) ||
                    (numbers[i - 1] > numbers[i] && numbers[i + 1] > numbers[i]))
    {
        count++;
        max = Math.Max(count, max);
    }
    else if ((numbers[i - 1] < numbers[i]) || (numbers[i - 1] > numbers[i])
                || ((numbers[i] < numbers[i + 1]) || (numbers[i] > numbers[i + 1])))
    {
        max = Math.Max(max, 2);
        count = 2;
    }
}
Console.WriteLine(max); // 14
于 2012-08-07T22:06:32.923 回答
2

我现在不是来自带有编译器的电脑，所以我只是尝试一下：

int max = 0;
int aux =0;
for(int i = 2 ; i < length; ++i)
{
    if (!((numbers[i - 2] > numbers[i - 1] && numbers[i - 1] < numbers[i]) ||
           numbers[i - 2] < numbers[i - 1] && numbers[i - 1] > numbers[i]))
    {
        aux = i - 2;
    }
    max = Math.Max(i - aux,max);
}
if (max > 0 && aux >0)
    ++max;

注意：应该适用于至少 3 个元素的序列。

于 2012-08-07T22:02:16.850 回答
2

这就是我的想法

  • 首先，你需要知道你是从高开始还是从低开始。例如：1-2-1或2-1-2。你甚至可能没有交替对。
  • 然后，您随后考虑每个数字，看看它是否属于序列，同时考虑当前方向。
  • 每次序列中断时，您都需要通过检查方向重新开始。

我不确定是否有可能在您已经看到的数字中，选择不同的起始数字可能会生成更长的序列。也许有一个定理表明这是不可能的；也许这很明显，我想多了。但我认为这是不可能的，因为一个序列被打破的原因是因为你有两个高点或两个低点，而且没有办法解决这个问题。

我假设以下情况

  • {}- 没有元素，返回 0
  • {1}- 单个元素，返回 0
  • {1, 1, 1}- 没有交替序列，返回 0

对超出 C# 预期的输入没有限制。大概可以浓缩吧。不确定是否有一种方法可以在不明确跟踪方向的情况下捕获方向变化逻辑。

static int max_alternate(int[] numbers)
{
  int maxCount = 0;
  int count = 0;
  int dir = 0; // whether we're going up or down

  for (int j = 1; j < numbers.Length; j++)
  {
      // don't know direction yet
      if (dir == 0)
      {
          if (numbers[j] > numbers[j-1])
          {
              count += 2; // include first number
              dir = 1; // start low, up to high
          }
          else if (numbers[j] < numbers[j-1])
          {
              count += 2;
              dir = -1; // start high, down to low
          }
      }
      else
      {
          if (dir == -1 && numbers[j] > numbers[j-1])
          {
              count += 1;
              dir = 1; // up to high
          }
          else if (dir == 1 && numbers[j] < numbers[j-1])
          {
              count += 1;
              dir = -1; // down to low
          }
          else 
          {
              // sequence broken
              if (count > maxCount)
              {
                  maxCount = count;
              }
              count = 0;
              dir = 0;
          }
      }
  }
  // final check after loop is done
  if (count > maxCount)
  {
      maxCount = count;
  }
  return maxCount;
}

以及一些基于我对问题的理解和一些假设的结果的测试用例。

static void Main(string[] args)
{

    int[] nums = { 1};            // base case == 0
    int[] nums2 = { 2, 1 };       // even case == 2
    int[] nums3 = { 1, 2, 1 };    // odd case == 3
    int[] nums4 = { 2, 1, 2 };    // flipped starting == 3
    int[] nums5 = { 2, 1, 2, 2, 1, 2, 1 }; // broken seqeuence == 4
    int[] nums6 = { 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1 }; // long sequence == 14
    Console.WriteLine(max_alternate(nums));
    Console.WriteLine(max_alternate(nums2));
    Console.WriteLine(max_alternate(nums3));
    Console.WriteLine(max_alternate(nums4));
    Console.WriteLine(max_alternate(nums5));
    Console.WriteLine(max_alternate(nums6));
    Console.ReadLine();
}
于 2012-08-07T23:49:59.480 回答
1

可能有很多方法可以解决这个问题，但这里有一个选择：

var numbers = new int[] { 7,1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1 };
int maxCount = 0;
for (int j = 0; j+1 < numbers.Length; j++)
{
    int count = 0;
    if (numbers[j] < numbers[j+1])
    {
        count += 2;
        for (int i = j+2; i+1 < numbers.Length; i += 2)
        {
            if (numbers[i] < numbers[i + 1] )
            {
                count += 2;
            }
            else
            {
                break;
            }
        }
    }
    if (maxCount < count)
    {
        maxCount = count;
    }
}
Console.WriteLine(maxCount);
Console.ReadLine();

此解决方案假定您需要相同的两个交替数字的序列。如果这不是要求，您可以更改第二个if.

现在它已经写出来了，它看起来比我想象的要复杂......也许其他人可以提出更好的解决方案。

于 2012-08-07T21:51:04.023 回答
0

假设至少有 2 个元素。

int max = 1;
bool expectGreaterThanNext = (numbers[0] > numbers[1]);
int count = 1;

for (var i = 0; i < numbers.Length - 1; i++)
{
    if (numbers[i] == numbers[i + 1] || expectGreaterThanNext && numbers[i] < numbers[i + 1])
    {
        count = 1;
        expectGreaterThanNext = (i != numbers.Length - 1) && !(numbers[i] > numbers[i+1]);
        continue;
    }
    count++;
    expectGreaterThanNext = !expectGreaterThanNext;

    max = Math.Max(count, max);
}
于 2012-08-08T00:39:15.780 回答
-2

这适用于任何整数，它跟踪低-高-低和高-低-就像你问的那样。

int numbers[] = new int[] { 1,2,1,2,1,2,1,2,1,2,1,2,1,2,2,2,1,2,1 };

   int count = 0;
   int updownup = 0;
   int downupdown = 0;
   for(int x = 0;x<=numbers.Length;x++)
   {
      if(x<numbers.Length - 2)
      {
         if(numbers[x]<numbers[x+1])
         {
          if(numbers[x+1]>numbers[x+2])
           {
           downupdown++; 
            }
         }

    }
}
count = 0;
for(x=0;x<=numbers.Length;x++)
{
  if(x<numbers.Length - 2)
  {
    if(numbers[x]>numbers[x+1]
    {
     if(numbers[x+1]<numbers[x+2])
     {
        updownup++;
        }
    }
    }

}
于 2012-08-07T22:08:26.230 回答