MaxDoubleスライスカダネのアルゴリズムのバリエーションを解決する

Question

私は、コードの問題を解決することによって自分のスキルを高めようとしていました。私はこの1つに達し：https://codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/

私は実際には、理論的に解決策を理解する：アレイ上

1. 使用Kadaneのアルゴリズムを、すべての指標で合計を格納します。
2. アレイを逆にして同じ操作を行います。
3. 一度に両方の結果セットを1つずつループすることによって、両方の合計が最大である点を見つけます。
4. maxは最大ダブルスライスです。

私の質問は、この問題の解決方法に関するものではありません。私の質問は、これがこの問題を解決できる方法であると想像する方法についてです。使用なされる必要があるで、少なくとも3種類の概念があります。

1. は、アレイ内のすべての要素が正、または負の場合、それはいくつかの正と負があるときとは異なる場合があることを理解配列内の要素Kadaneのアルゴリズム

3. は、前方アレイの上に行くと逆転しました。

これにもかかわらず、Codalityはこの問題を「痛い」とタグ付けしています。

私の質問には何か不足していますか？これらの概念のいくつかを知らなくてもこの問題を解決することは難しいようです。

私はゼロから始め、非常に基本的なコンセプトから始めることができ、この問題を解決するために必要なコンセプトに到達するための手法はありますか？それとも、問題を開始する前にこれらの概念を知っていると予想されますか？

今後の必要な概念がわからないような問題を解決するために自己を準備するにはどうすればよいですか？

Answer 1

私はあなたはそれがあるよりも、それがより難しい理由です、あなたが問題をoverthinkingていると思う：

アレイ内のすべての要素が正、または負の場合、それはより異なる場合であることを理解配列にはいくつかの正と負の要素があります。

別のケースである必要はありません。とにかくこの区別を気にせずに動作するアルゴリズムを考え出すことができます。

この区別を理解することから始める必要はありません。だからといって、それまで考える必要はありません。

Kadaneのアルゴリズム

問題は、必要とするものを考え、アルゴリズムを考えてはいけません。通常、10 +段落の問題文は、はるかに少なく表現できます。

問題文を簡単にする方法を見てみましょう。

まず、スライスをトリプレットとして定義します。(x, y, z)。これは、x+1で始まり、z-1で終わり、yを含まない要素の合計で定義されます。

次に、最大合計スライスを求めます。最大スライスが必要な場合は、定義にxとzが必要ですか？私たちは最大の合計を得る限り、どこからでも開始して終了させることができますか？

スライスを配列のサブセットとして再定義すると、どこでも起動し、y-1になり、y+1から続きます。ずっと簡単ですね。

このようなスライスは最大限必要です。

yごとに、y+1で始まる最大合計サブアレイとy-1で終了する最大合計サブアレイが必要になると考えられます。これらを見つけることができる場合は、それぞれyのグローバル最大値を更新できます。

どうやってこれを行うのですか？これは、あなたが望むものの半分を行うKadaneのアルゴリズムを指すはずです：最大和サブアレイがいくつかで終わります。xで終わります。

kadane(y - 1) + kadane_reverse(y + 1) 

をし、グローバル最大と比較：あなたは、両側からそれを計算するのであれば、各yのために、あなただけ見つけなければなりません。

ネガとポジティブの特別なケースはありません。考えていない "Kadane's！"あなたが問題を見るとすぐに。

考え方は、その意味を変えずに、できるだけ要件を単純化することです。次に、アルゴリズムと演繹スキルを使用してソリューションに到達します。これらのスキルは時間と経験に磨かれています。