変数を、あらかじめ設定した数字から選びたい

Question

競技プログラミングの問題を解いています。
######【問題】
######ｎ本の棒がある。棒 i の長さは Ai である。それらの棒から３本を選んで、できるだけ周長の長い三角形を作ろうと考えている。最大の周長を求めよ。ただし、三角形が作れない際には０を答えとしなさい。
＊制約
・３≦ｎ≦１００
・１≦Ai≦１０＾６

例：
入力
ｎ＝５
A＝｛２, ３, ４, ５, １０｝

出力
１２（３, ４, ５の棒を選んだとき）

この問題を Kotlin を用いて解いており、以下のコードまで完成いたしました。

fun main(){
    val n = readLine()!!.toInt()
    val sides = readLine()!!.split(" ").map(String::toInt)
    val ans = 0

    (0..n).forEach { k ->
        (0..(n - 1)).forEach { j ->
            (0..(n - 2)).forEach { i ->
                val circumference = i + j + k
                val twoSides = j + k
                when {
                    twoSides > i -> {
                        println(circumference)
                        return
                    }
                }
            }
        }
        println(ans)
    }
}

ここまで書いたところ、この i, j, k が sides がつながっていないことに気づいたのですが、つなげ方がわかりません。
map や range を使用すればいいのでしょうか？また、このコードで本当に問題の条件をクリアしているのでしょうか？

i, j, k を sides から選ぶようにするための方法を教えていただきたく存じます。

追：Android Studio を使用しております。

Comments

[Zuishin]

配列なので添え字を使えばいいんですが、それ以前にアルゴリズムが間違っていませんか？
長い方から選ばないと。

[Liao]

回答ありがとうございます。
初心者質問で申し訳ないのですが、以下の
(0..n).forEach { i ->
(0..(n - 1)).forEach { j ->
(0..(n - 2)).forEach { k ->
というコードは、長い辺 → 短い辺 ではなく、短い辺 → 長い辺 を表すということでよろしいでしょうか？

[Zuishin]

そこは尋ねなくても試してみればわかることですが、そもそもソートされている保証がないなら、その前にソートしなければいけません。

とりあえず配列じゃなくて List の間違いだったので、List の使い方を調べてください。

[Liao]

わかりました

Answer 1

アルゴリズムのタグがついていたので、直接の回答にはなっていませんが…

1. Aiを大きい順に並べ替えた数列Bjを考えます。

2. B1,B2,B3で三角形が作れるか調べます。作れる場合、その和が答えになります。

3. 作れない場合、B1を使うどの組み合わせも三角形を作れないので、B2,B3,B4で作れるか調べます。作れる場合、その和が答えになります。作れない場合、B3,B4,B5、というように、添字を1つづつ増やして同様に調べ、Bnを使っても作れない場合、0が答えになります。

全ての組み合わせを調べた場合、計算量はO(n^3)ですが、このアルゴリズムの場合、計算量はO(nlogn)になります。

Comments

[Liao]

回答ありがとうございます。
たしかに、この方法なら早く済みそうですし、わかりやすいです。
この方法でさっそくコードを書き直そうと思います。
ありがとうございました。