配列 arr[] 内の abs(i - j) * min(arr[i], arr[j]) の最大値を求める
n 個の異なる要素の配列が与えられたとします。配列内の 2 つの数値の最小値とその位置の差の絶対値の積の最大値を求めます。つまり、abs(i - j) * min(arr[i] arr[j]) の最大値を求めます。ここで、i と j は 0 から n-1 まで変化します。
例:
Input : arr[] = {3 2 1 4} Output: 9 // arr[0] = 3 and arr[3] = 4 minimum of them is 3 and // absolute difference between their position is // abs(0-3) = 3. So product is 3*3 = 9 Input : arr[] = {8 1 9 4} Output: 16 // arr[0] = 8 and arr[2] = 9 minimum of them is 8 and // absolute difference between their position is // abs(0-2) = 2. So product is 8*2 = 16 Recommended Practice 最大値を求める 試してみてください! あ 簡単な解決策 この問題は、各要素を 1 つずつ取り出して、この要素をその右側の要素と比較することです。次に、それらの最小値とそれらのインデックス間の絶対差の積を計算し、結果を最大化します。このアプローチの時間計算量は O(n^2) です。
アン 効率的なソリューション 線形時間計算量で問題を解決します。 2 つのイテレータを使用します 左=0 そして 右=n-1 要素 arr[Left] と arr[right] を比較します。
left = 0 right = n-1 maxProduct = -INF While (left < right) If arr[Left] < arr[right] currProduct = arr[Left]*(right-Left) Left++ . If arr[right] < arr[Left] currProduct = arr[Right]*(Right-Left) Right-- . maxProduct = max(maxProduct currProduct)
以下は上記のアイデアを実装したものです。
C++ // C++ implementation of code #include using namespace std ; // Function to calculate maximum value of // abs(i - j) * min(arr[i] arr[j]) in arr[] int Maximum_Product ( int arr [] int n ) { int maxProduct = INT_MIN ; // Initialize result int currProduct ; // product of current pair // loop until they meet with each other int Left = 0 right = n -1 ; while ( Left < right ) { if ( arr [ Left ] < arr [ right ]) { currProduct = arr [ Left ] * ( right - Left ); Left ++ ; } else // arr[right] is smaller { currProduct = arr [ right ] * ( right - Left ); right -- ; } // maximizing the product maxProduct = max ( maxProduct currProduct ); } return maxProduct ; } // Driver program to test the case int main () { int arr [] = { 8 1 9 4 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); cout < < Maximum_Product ( arr n ); return 0 ; }
Java // Java implementation of code import java.util.* ; class GFG { // Function to calculate maximum value of // abs(i - j) * min(arr[i] arr[j]) in arr[] static int Maximum_Product ( int arr [] int n ) { // Initialize result int maxProduct = Integer . MIN_VALUE ; // product of current pair int currProduct ; // loop until they meet with each other int Left = 0 right = n - 1 ; while ( Left < right ) { if ( arr [ Left ] < arr [ right ] ) { currProduct = arr [ Left ] * ( right - Left ); Left ++ ; } // arr[right] is smaller else { currProduct = arr [ right ] * ( right - Left ); right -- ; } // maximizing the product maxProduct = Math . max ( maxProduct currProduct ); } return maxProduct ; } // Driver code public static void main ( String [] args ) { int arr [] = { 8 1 9 4 }; int n = arr . length ; System . out . print ( Maximum_Product ( arr n )); } } // This code is contributed by Anant Agarwal.
Python3 # Python implementation of code # Function to calculate # maximum value of # abs(i - j) * min(arr[i] # arr[j]) in arr[] def Maximum_Product ( arr n ): # Initialize result maxProduct = - 2147483648 # product of current pair currProduct = 0 # loop until they meet with each other Left = 0 right = n - 1 while ( Left < right ): if ( arr [ Left ] < arr [ right ]): currProduct = arr [ Left ] * ( right - Left ) Left += 1 else : # arr[right] is smaller currProduct = arr [ right ] * ( right - Left ) right -= 1 # maximizing the product maxProduct = max ( maxProduct currProduct ) return maxProduct # Driver code arr = [ 8 1 9 4 ] n = len ( arr ) print ( Maximum_Product ( arr n )) # This code is contributed # by Anant Agarwal.
C# // C# implementation of code using System ; class GFG { // Function to calculate maximum // value of abs(i - j) * min(arr[i] // arr[j]) in arr[] static int Maximum_Product ( int [] arr int n ) { // Initialize result int maxProduct = int . MinValue ; // product of current pair int currProduct ; // loop until they meet // with each other int Left = 0 right = n - 1 ; while ( Left < right ) { if ( arr [ Left ] < arr [ right ]) { currProduct = arr [ Left ] * ( right - Left ); Left ++ ; } // arr[right] is smaller else { currProduct = arr [ right ] * ( right - Left ); right -- ; } // maximizing the product maxProduct = Math . Max ( maxProduct currProduct ); } return maxProduct ; } // Driver code public static void Main () { int [] arr = { 8 1 9 4 }; int n = arr . Length ; Console . Write ( Maximum_Product ( arr n )); } } // This code is contributed by nitin mittal.
PHP // PHP implementation of code // Function to calculate // maximum value of // abs(i - j) * min(arr[i] // arr[j]) in arr[] function Maximum_Product ( $arr $n ) { $INT_MIN = 0 ; // Initialize result $maxProduct = $INT_MIN ; // product of current pair $currProduct ; // loop until they meet // with each other $Left = 0 ; $right = $n - 1 ; while ( $Left < $right ) { if ( $arr [ $Left ] < $arr [ $right ]) { $currProduct = $arr [ $Left ] * ( $right - $Left ); $Left ++ ; } // arr[right] is smaller else { $currProduct = $arr [ $right ] * ( $right - $Left ); $right -- ; } // maximizing the product $maxProduct = max ( $maxProduct $currProduct ); } return $maxProduct ; } // Driver Code $arr = array ( 8 1 9 4 ); $n = sizeof ( $arr ) / sizeof ( $arr [ 0 ]); echo Maximum_Product ( $arr $n ); // This code is contributed // by nitin mittal. ?>
JavaScript < script > // Javascript implementation of code // Function to calculate // maximum value of // abs(i - j) * min(arr[i] // arr[j]) in arr[] function Maximum_Product ( arr n ) { let INT_MIN = 0 ; // Initialize result let maxProduct = INT_MIN ; // Product of current pair let currProduct ; // Loop until they meet // with each other let Left = 0 right = n - 1 ; while ( Left < right ) { if ( arr [ Left ] < arr [ right ]) { currProduct = arr [ Left ] * ( right - Left ); Left ++ ; } // arr[right] is smaller else { currProduct = arr [ right ] * ( right - Left ); right -- ; } // Maximizing the product maxProduct = Math . max ( maxProduct currProduct ); } return maxProduct ; } // Driver Code let arr = new Array ( 8 1 9 4 ); let n = arr . length ; document . write ( Maximum_Product ( arr n )); // This code is contributed by Saurabh Jaiswal < /script>
出力
16
時間計算量 : O(N log N) ここで N は配列の長さです。
空間の複雑さ : O(1) 余分なスペースが使用されないため。
これはどのように作動しますか？
上記の線形アルゴリズムで潜在的なペアを見逃していないことを示すことが重要です。つまり、left++ または right-- を実行しても、maxProduct のより高い値が得られるケースが発生しないことを示す必要があります。
常に (right - left) を乗算することに注意してください。
- 到着した場合[左] < arr[right] then smaller values of 右 for current left は、maxProduct のより高い値を生成できないため役に立ちません (arr[left] と (right - left) を乗算するため)。 arr[left] がその左側のどの要素よりも大きい場合はどうなるでしょうか。その場合、その要素にとってより適切なペアが現在の権限で見つかっている必要があります。したがって、現在の left とのより良いペアを見逃すことなく、安全に left を増やすことができます。
- arr[right] の場合も同様の引数が適用されます。 < arr[left].
