最後に、問題の解決策を見つけました。お気軽にコメントしてください。
例を見てみましょう:
int a[] = {1,3,4,6,10,6,16,12,13,15,16,19,20,22,25}
これをグラフに入れると (X 座標 -> 配列インデックスおよび Y 座標 -> 配列の値)、グラフは次のようになります。
グラフを見ると、ディップが発生する場所が 2 つあります。1 つは 10 の後、もう 1 つは 16 の後です。ジグザグ部分では、最小値が 6 で最大値が 16 であることがわかります。配列全体をソートするのは (6,16) の間です。以下の画像を参照してください。
これで、配列を簡単に 3 つの部分に分割できます。中央部分は、配列全体がソートされるようにソートしたい部分です。貴重な情報を提供してください。私は自分のレーベルに説明するのに最善を尽くしました。もっと説明したい場合はお知らせください。貴重なご意見お待ちしております。
以下のコードは、上記のロジックを実装しています。
public void getMN(int[] a)
{
int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE;
for(int i=1; i<a.length; i++)
{
if(a[i]<a[i-1])
{
if(a[i-1] > max)
{
max = a[i-1];
}
if(a[i] < min)
{
min = a[i];
}
}
}
if(max == Integer.MIN_VALUE){System.out.println("Array already sorted!!!");}
int m =-1, n =-1;
for(int i=0; i<a.length; i++)
{
if(a[i]<=min)
{
m++;
}
else
{
m++;
break;
}
}
for(int i=a.length-1; i>=0; i--)
{
if(a[i]>=max)
{
n++;
}
else
{
n++;
break;
}
}
System.out.println(m +" : "+(a.length-1-n));
System.out.println(min +" : "+max);
}