Algorithms/Dynamic Programming/Longest Increasing Subsequence

Last-modified: 2008-05-23 (金) 11:00:51

Longest Inc/Dec-reasing Subsequence

Program

int data[MAX];
int result[MAX];

void LIS() {
  fill(result, result + MAX, 0);

  for(int i = 0 ; i < MAX - 1 ; i++) {
    for(int j = i + 1 ; j < MAX ; j++) {
      if(data[j] > data[i]) {
        if(result[i] + 1 > result[j]) {
          result[j] = result[i] + 1;
        }
      }
    }
  }
}