Largest Ratio Contiguous subarray
Given an array arr[] of N numbers, the task is to find the largest ratio of contiguous subarray from the given array.
Examples:
Input: arr = { -1, 10, 0.1, -8, -2 }
Output: 100
Explanation:
The subarray {10, 0.1} gives 10 / 0.1 = 100 which is the largest ratio.Input: arr = { 2, 2, 4, -0.2, -1 }
Output: 20
Explanation:
The subarray {4, -0.2, -1} has the largest ratio as 20.
Approach: The idea is to generate all the subarrays of the array and for each subarray, find the ratio of the subarray as arr[i] / arr[i+1] / arr[i+2] and so on. Keep track of the maximum ratio and return it at the end.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to return maximum // of two double values double maximum( double a, double b) { // Check if a is greater // than b then return a if (a > b) return a; return b; } // Function that returns the // Ratio of max Ratio subarray double maxSubarrayRatio( double arr[], int n) { // Variable to store // the maximum ratio double maxRatio = INT_MIN; // Compute the product while // traversing for subarrays for ( int i = 0; i < n; i++) { for ( int j = i; j < n; j++) { double ratio = arr[i]; for ( int k = i + 1; k <= j; k++) { // Calculate the ratio ratio = ratio / arr[k]; } // Update max ratio maxRatio = maximum(maxRatio, ratio); } } // Print the answer return maxRatio; } // Driver code int main() { double arr[] = { 2, 2, 4, -0.2, -1 }; int n = sizeof (arr) / sizeof (arr[0]); cout << maxSubarrayRatio(arr, n); return 0; } |
Java
// Java program for the above approach class GFG{ // Function to return maximum // of two double values static double maximum( double a, double b) { // Check if a is greater // than b then return a if (a > b) return a; return b; } // Function that returns the // Ratio of max Ratio subarray static double maxSubarrayRatio( double arr[], int n) { // Variable to store // the maximum ratio double maxRatio = Integer.MIN_VALUE; // Compute the product while // traversing for subarrays for ( int i = 0 ; i < n; i++) { for ( int j = i; j < n; j++) { double ratio = arr[i]; for ( int k = i + 1 ; k <= j; k++) { // Calculate the ratio ratio = ratio / arr[k]; } // Update max ratio maxRatio = maximum(maxRatio, ratio); } } // Print the answer return maxRatio; } // Driver code public static void main(String[] args) { double arr[] = { 2 , 2 , 4 , - 0.2 , - 1 }; int n = arr.length; System.out.println(maxSubarrayRatio(arr, n)); } } // This code is contributed by rutvik_56 |
Python3
# Python3 program for the above approach import sys # Function to return maximum # of two double values def maximum(a, b): # Check if a is greater # than b then return a if (a > b): return a return b # Function that returns the # Ratio of max Ratio subarray def maxSubarrayRatio(arr, n): # Variable to store # the maximum ratio maxRatio = - sys.maxsize - 1 # Compute the product while # traversing for subarrays for i in range (n): for j in range (i, n): ratio = arr[i] for k in range (i + 1 , j + 1 ): # Calculate the ratio ratio = ratio / / arr[k] # Update max ratio maxRatio = maximum(maxRatio, ratio) # Print the answer return int (maxRatio) # Driver code if __name__ = = "__main__" : arr = [ 2 , 2 , 4 , - 0.2 , - 1 ] n = len (arr) print (maxSubarrayRatio(arr, n)) # This code is contributed by chitranayal |
C#
// C# program for the above approach using System; class GFG{ // Function to return maximum // of two double values static double maximum( double a, double b) { // Check if a is greater // than b then return a if (a > b) return a; return b; } // Function that returns the // Ratio of max Ratio subarray static double maxSubarrayRatio( double []arr, int n) { // Variable to store // the maximum ratio double maxRatio = int .MinValue; // Compute the product while // traversing for subarrays for ( int i = 0; i < n; i++) { for ( int j = i; j < n; j++) { double ratio = arr[i]; for ( int k = i + 1; k <= j; k++) { // Calculate the ratio ratio = ratio / arr[k]; } // Update max ratio maxRatio = maximum(maxRatio, ratio); } } // Print the answer return maxRatio; } // Driver code public static void Main(String[] args) { double []arr = { 2, 2, 4, -0.2, -1 }; int n = arr.Length; Console.WriteLine(maxSubarrayRatio(arr, n)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach // Function to return maximum // of two double values function maximum(a, b) { // Check if a is greater // than b then return a if (a > b) return a; return b; } // Function that returns the // Ratio of max Ratio subarray function maxSubarrayRatio(arr, n) { // Variable to store // the maximum ratio var maxRatio = -1000000000; // Compute the product while // traversing for subarrays for ( var i = 0; i < n; i++) { for ( var j = i; j < n; j++) { var ratio = arr[i]; for ( var k = i + 1; k <= j; k++) { // Calculate the ratio ratio = ratio / arr[k]; } // Update max ratio maxRatio = maximum(maxRatio, ratio); } } // Print the answer return maxRatio; } // Driver code var arr = [ 2, 2, 4, -0.2, -1 ]; var n = arr.length; document.write( maxSubarrayRatio(arr, n)); // This code is contributed by rrrtnx. </script> |
Output
20
Time Complexity: (N3)
Auxiliary Space: O(1)