■

プログラミングコンテストチャレンジブックを題材に勉強会をやっている。今日の課題は、p63の最長増加部分列問題だった。で、本の回答が、下記。

static int SaichoZoka(params int[] a)
{
  var dp = new int[a.Length + 1];
  for (int i = 0; i < a.Length; ++i)
  {
    dp[i + 1] = 1;
    for (int j = 0; j < i; ++j)
      if (a[j] < a[i])
        dp[i + 1] = Math.Max(dp[i + 1], dp[j] + 1);
  }
  return dp[a.Length];
}

しかし、p64の漸化式と合っていない。結果も正しくない。漸化式通りなら下記。

static int SaichoZoka(params int[] a)
{
  var dp = new int[a.Length];
  for (int i = 0; i < a.Length; ++i)
  {
    dp[i] = 1;
    for (int j = 0; j < i; ++j)
      if (a[j] < a[i])
        dp[i] = Math.Max(dp[i], dp[j] + 1);
  }
  return dp[a.Length - 1];
}

ただし、これも間違い。正しくは、最後の行は、return dp.Max(); となる。