수조 최장 증가자 서열

이 문제는 매트릭스 곱하기와 비교적 비슷하지만 A[1...j]의 대가만 계산하기 때문에 매트릭스 곱하기보다 순환이 적고 매트릭스 상칭의 복잡도는 n의 3차원이며 이 문제의 복잡도는 n제곱이다.데이터를 출력하려면 약간의 우여곡절을 겪었기 때문에 잘 이해해야 한다. 그 중에서 귀속이 종료되는 조건은 수조가 기록한 위치와 자신의 위치가 같지만 이 위치의 데이터도 출력해야 하기 때문에else문장에서 가장 앞에 있는 어떤 데이터를 출력해야 한다. 또한 마지막 데이터는 임시 변수에 저장하고 창고에 눌러 넣고 귀속이 돌아올 때 데이터를 출력해야 한다. 전체 작성 사고방식 시뮬레이션 행렬이 서로 곱하는 사고방식이다.프로그램은 다음과 같습니다.

// LIS[1,j] = max{LIS[1,k] + 1, 1}
#include <stdio.h>
#include <vector>
#include <boost/scoped_ptr.hpp>
void Print(int value) {
  printf("%d ", value);
}
 
template<typename T, typename VisitFun>
void PrintSubarray(const std::vector<T>& array, const size_t* array_offset, size_t position, VisitFun visit_fun) {
  if (position != array_offset[position]) {
    size_t to_print = position;
    PrintSubarray(array, array_offset, array_offset[position], visit_fun);
    visit_fun(array[to_print]);
  } else {
    visit_fun(array[position]);
  }
}
template<typename T>
void LongestIncreaseSubarray(const std::vector<T>& array) {
  size_t max = 0;
  size_t max_position = 0;
  boost::scoped_ptr<size_t> max_length_buffer(new size_t[array.size()]);
  size_t* max_length = max_length_buffer.get();
  boost::scoped_ptr<size_t> array_offset_buffer(new size_t[array.size()]);
  size_t* array_offset = array_offset_buffer.get();
  for (size_t length = 1; length <= array.size(); ++length) {
    max_length[length - 1] = 1;
    array_offset[length -1] = length - 1;
    for (size_t k = 0; k < length; ++k) {
      if (array[k] < array[length - 1] && max_length[k] + 1 > max_length[length - 1]) {
          max_length[length - 1] = max_length[k] + 1;
          array_offset[length - 1] = k;
          if (max_length[length - 1] > max) {
            max = max_length[length - 1];
            max_position = length -1;
            printf("%zd
", max_position);
          }
      }
    }
    printf("--%zd
", max_length[length - 1]);      
  }
  for (int i = 0; i < array.size(); ++i) {
    printf("%zd ", array_offset[i]);
  }
  printf("
");
  PrintSubarray(array, array_offset, max_position, Print);
}
int main(int argc, char** argv) {
  int array_buffer[] = {1, 0, 1,4,5,2,6,1,7,2,8};
  std::vector<int> array(array_buffer, array_buffer + sizeof(array_buffer) / sizeof(int));
  LongestIncreaseSubarray(array);
}