Let's suppose the array is A={1,2,3} , now get all subarrays for this array. For each sub-array find the minimum in that sub-array, also find the sum of items in that sub-array. Finally add all these values. The input cannot be sorted as I want all possible subarrays.
Example:
Possible sub-arrays are:
{1} - min = 1, sum = 1 => min* sum = 1
{1,2} - min = 1, sum = 3 => min* sum = 3
{1,2,3} - min = 1, sum = 6 => min* sum = 6
{2} - min = 2, sum = 2 => min* sum = 4
{2,3} - min = 2, sum = 5 => min* sum = 10
{3} - min = 3, sum = 3 => min* sum = 9
Finally add all these values to get the result = 1 + 3 + 6 + 4 + 10 + 9 = 33.
constraints: array elements can range from 1 to 1000_000_000. Array size from 1 to 100_000. Return output as module 7+1000_000_000.
Here is my program with O(n^2). I want a better algorithm with lesser time complexity.
public int program(int[] A, int n) {
int M = 7 + 1000_000_000;
long total = 0;
for (int i = 0; i < n; i++) {
long sum = 0;
int min = A[i];
for (int j = i; j < n; j++) {
int a = A[j];
sum= (sum + a) % M;
min = Math.min(min, a);
total = (total + (min * sum) % M) % M;
}
}
return (int) total;
}
Input range:
n range is 1 to 10^6
elements in array range is 1 to 10^9
you can try using recursion.
int[] array = {1,2,3};
int maxSum = totalOfSubArray(array, 0, 0);
private static int totalOfSubArray(int[] arr, int currentIndex, int maxSum) {
int currentSum = 0;
if (currentIndex == arr.length) {
System.out.println("final total: " + maxSum);
return maxSum;
}
String result = "";
for (int i = currentIndex; i < arr.length; i++) {
result += arr[i];
currentSum += arr[i];
int min = Math.min(arr[currentIndex], arr[i]);
maxSum += min * currentSum;
System.out.println("[" + result + "] min : " + min + " currentSum: " + currentSum + " maxSum: " + maxSum);
}
return totalOfSubArray(arr, currentIndex + 1, maxSum);
}