文字列と各文字の値を与えるオンラインテストの問題がありました。各文字の値は [-10, 10] の範囲です。問題は、同じ文字で開始および終了し、最大値を持つ部分文字列を見つけることでした。この問題は、文字を値に置き換えた後、部分配列の最大合計問題の拡張バージョンに簡単に縮小されます。制約は、開始値と終了値が同じになることです。私は素朴な解決策を思いつきましたが、十分ではありませんでした。Kadane のアルゴリズムまたは時間の複雑さが改善された他のアルゴリズムでこれを解決する方法を誰か教えてもらえますか?