Problem from @goura

gistfile1.py

#! -*- coding: utf-8 -*-
'''
Problem:
The input is a sequence of digits consistent of 0-9.
We define "increasing subsequence", when the substring consists of
consecutive numbers (NOT including equal). For instance, 0369, 3478, 58.
Please write a program (using C, Java, PHP, Ruby or Python)
to find the longest increasing subsequence of numbers in the given
string.

問題:
入力値は、数字（0-9）からなる文字列とする。
前から順に数字が大きくなっているとき、その文字列は「単調増加」であると定義する。
例えば、0369、3478、58は単調増加である。
与えられた数字からなる文字列から、単調増加な部分文字列のうち最も長いものを検索する
プログラムを書け (言語は C、Java、PHP、Ruby、Python)。
'''

def strict_increasing_initial_segment(sequence):
  '''
  >>> strict_increasing_initial_segment([9, 8, 7])
  [9]
  >>> strict_increasing_initial_segment([7, 9, 8])
  [7, 9]
  >>> strict_increasing_initial_segment([7, 8, 9])
  [7, 8, 9]
  '''
  sequence = iter(sequence)
  initial_segment = [next(sequence)]
  for n in sequence:
    if n <= initial_segment[-1]:
      break
    initial_segment.append(n)
  return initial_segment


def strict_increasing_subsequences(sequence):
  sequence = list(sequence)
  for i in range(len(sequence)):
    yield strict_increasing_initial_segment(sequence[i:])


def lcn(numbers):
  '''
  >>> lcn('28172381289562158357138523812128123')
  '1289'
  >>> lcn('281723812895621583571385238123456128123')
  '123456'
  '''
  numbers = [int(s) for s in numbers]
  longest_subseq = max(strict_increasing_subsequences(numbers), key=len)
  return ''.join(map(str, longest_subseq))


if __name__ == '__main__':
  import doctest
  doctest.testmod()