Javaプログラミング配列の中で最大のサブマトリックスを簡単に解法してコードを実現します。
本論文で研究したのは主にJavaプログラミング配列における最大サブ行列の関連内容であり、以下のように具体的に紹介している。
いい人に出会ったら、一生を変えることができます。いい本に出会ったら、何を味わっていますか？
最近は左程雲さんの『プログラマコード面接ガイドCIT名企業アルゴリズムとデータ構造テーマの最適解』を見ていて、とても悟りました。この方面の趣味があるブロ友も見学に行くことを提案します。
本で説明したスタックベースの一番大きな行列のアルゴリズムは古典的ですが、博主の能力は限られていて、このアルゴリズムの精髄を徹底的に理解できませんでした。しかし、この思想によって博主は簡単にこのような問題に対処するアルゴリズムを考え出しました。
中心となる思想
まず図を見てみましょう。私たちは大体のことが分かります。
図のように、毎回は一回の計算ですが、私達の核心はこの順番ごとの内部演算です。
各レイヤーの連続して連続する最大の長さを計算します。
つまり、私たちは最もこの配列で下から上までの輪回計算を行い、そして各ラウンドに対して本ラウンドで導出できる連続最大サブ行列の面積を計算することができます。そして、各ラウンドの最大のデータを比較するだけで、その配列の最大の連続するサブマトリックスの面積が求められます。
コード
はい、上の核心思想の下地があれば、コードの作成に着手できます。私もはっきり言っていないと思いますが、ご了承ください。
テスト
配列をテストします。まずは冒頭の写真に示されている配列でテストを行いましょう。
それから、配列の要素の値を変更して、さらにテストして、結果が正しいかどうかを確認します。
ブロガー本人が自らテストした結果、このアルゴリズムは正常に動作することができます。：
部分を最適化する
最適化の部分といえば、まず私たちが見られるのは、最後のステップで結果集の中の最大値を求めることでしょう。
確かに、私達は別の変数を申請して、これまでの車輪の最大のサブマトリックスの面積を記録することができます。しかし、この点の最適化には大きな役割を果たしていません。時間の複雑さもあまり改善されていません。
もう一つの点は、より良い切り口ができるということは、輪回ごとに演算するときに判断を加えて、現在の輪回の前に次の循環をするかどうかを決めることです。配列中の要素の変動が大きいなら、最適化の度合いはいいです。
締め括りをつける
このアルゴリズムは精巧で、唯一の残念なところは時間の複雑さがちょっと大きいです。もし読者が時間の複雑さの比較的小さいアルゴリズムを求めているなら、回り道してください。
結果を求めたいだけなら、いいです。少なくとも暴力的な方法より計算効率が高いです。
以上はJavaプログラミング配列の中で最も大きなサブ行列の簡便な解法についてコードの全部の内容を実現しました。興味のある方は引き続き当駅の他のテーマを参照してください。友達のサポートに感謝します。
いい人に出会ったら、一生を変えることができます。いい本に出会ったら、何を味わっていますか？
最近は左程雲さんの『プログラマコード面接ガイドCIT名企業アルゴリズムとデータ構造テーマの最適解』を見ていて、とても悟りました。この方面の趣味があるブロ友も見学に行くことを提案します。
本で説明したスタックベースの一番大きな行列のアルゴリズムは古典的ですが、博主の能力は限られていて、このアルゴリズムの精髄を徹底的に理解できませんでした。しかし、この思想によって博主は簡単にこのような問題に対処するアルゴリズムを考え出しました。
中心となる思想
まず図を見てみましょう。私たちは大体のことが分かります。
図のように、毎回は一回の計算ですが、私達の核心はこの順番ごとの内部演算です。
各レイヤーの連続して連続する最大の長さを計算します。
つまり、私たちは最もこの配列で下から上までの輪回計算を行い、そして各ラウンドに対して本ラウンドで導出できる連続最大サブ行列の面積を計算することができます。そして、各ラウンドの最大のデータを比較するだけで、その配列の最大の連続するサブマトリックスの面積が求められます。
コード
はい、上の核心思想の下地があれば、コードの作成に着手できます。私もはっきり言っていないと思いますが、ご了承ください。
package stack_and_queue;
/**
* @author <br>
*
*/
public class MaxRectangle {
public static void main(String[] args) {
Integer[] arr = { 2, 1, 3, 5, 7, 6, 4 };
Integer maxRectangle = maxRectangleArea(arr);
System.out.println(" ： " + maxRectangle);
}
/**
* @param arr
* @return
*/
private static Integer maxRectangleArea(Integer[] arr) {
int[] result = new int[arr.length];
// ，
for (int i = 1; i <= arr.length; i++) {
//
int templen = 0;
//
int templen_max = 0;
// ，
for (int j = 1; j <= arr.length; j++) {
if (arr[j - 1] >= i) {
templen += 1;
templen_max = templen;
} else {
templen = 0;
}
}
result[i - 1] = i * templen_max;
// System.out.println(" " + i + " ：" + templen_max);
}
// ，
int maxArea = 0;
for (int i = 0; i < result.length; i++) {
maxArea = maxArea > result[i] ? maxArea : result[i];
}
//
return maxArea;
}
}テスト
配列をテストします。まずは冒頭の写真に示されている配列でテストを行いましょう。
Integer[] arr = {2,1,3,5,7,6,4}
・・・それから、配列の要素の値を変更して、さらにテストして、結果が正しいかどうかを確認します。
Integer[] arr = {2,1,3,1,7,6,4}
・・・ブロガー本人が自らテストした結果、このアルゴリズムは正常に動作することができます。：
部分を最適化する
最適化の部分といえば、まず私たちが見られるのは、最後のステップで結果集の中の最大値を求めることでしょう。
確かに、私達は別の変数を申請して、これまでの車輪の最大のサブマトリックスの面積を記録することができます。しかし、この点の最適化には大きな役割を果たしていません。時間の複雑さもあまり改善されていません。
もう一つの点は、より良い切り口ができるということは、輪回ごとに演算するときに判断を加えて、現在の輪回の前に次の循環をするかどうかを決めることです。配列中の要素の変動が大きいなら、最適化の度合いはいいです。
締め括りをつける
このアルゴリズムは精巧で、唯一の残念なところは時間の複雑さがちょっと大きいです。もし読者が時間の複雑さの比較的小さいアルゴリズムを求めているなら、回り道してください。
結果を求めたいだけなら、いいです。少なくとも暴力的な方法より計算効率が高いです。
以上はJavaプログラミング配列の中で最も大きなサブ行列の簡便な解法についてコードの全部の内容を実現しました。興味のある方は引き続き当駅の他のテーマを参照してください。友達のサポートに感謝します。