線形時間で解決できる問題は、微調整して O(1) 補助空間を使用しないようにできることに気付きました。パス グラフの重み付き独立集合問題を取り上げます。総重量のみが必要な場合は、O(1) スペースが必要です。ただし、ソリューションで set も要求される場合は、O(n) スペースを使用しますが、使用される補助スペースは依然として O(1) です。線形時間アルゴリズムを認めるその他の問題は、最大部分配列合計問題、1D ベクトルを i 位置で回転させること、BST をソート済み二重連結リストに変換することなどです...