Print all subarray of given array and than store maximum integer in each subarray to get the sum of all maximum's?

Question

For Example - If given array is :- int[] arr = { 1, 4, 8, 3 };

The result Subarray should be:

1 , 
1 ,4 , 
1 ,4 ,8 , 
1 ,4 ,8 ,3 ,  

4 , 
4 ,8 , 
4 ,8 ,3 ,  

8 , 
8 ,3 ,
 
3 ,

and than , Maximum of each subarray are :- 1 ,4 ,8,8,4,8,8,8,8,3 therefore sum of all maximum should be :- 1 + 4 +8+8+4+8+8+8+8=3 = 60

To Write Subarray, I was able to do this with loop:-

{
            for(int j = i ; j <= n ; j++)
            {
                for(int k = i ; k < j ; k++)
                {
                    Console.Write(arr[k] + " ," );                
                    
                }
                
        Console.WriteLine(" " );
            }
        }
        
    }

After this, I was trying to store maximum values in the Dictionary data structure but was not able to find where exactly use dictionary structure and how to use Math.max statement.

IDictionary<int, int> maxValue = new Dictionary<int, int>();

You don't really need any of that. You can keep track of the max for the sub array, you are going through it to print it anyway. Then after iterating it just add max to total. — maraca, Feb 07 '22 at 18:56
Refer this one: https://stackoverflow.com/questions/55780200/intuition-behind-using-a-monotonic-stack for an `O(n)` solution using monotonic stacks (instead of maximums, it calculates the minimums). Your current approach would likely TLE. — Someone, Feb 07 '22 at 19:19
See also [this question](https://stackoverflow.com/q/70293944/16757174), which solves the case for maximums and minimums too, with a variety of methods. — kcsquared, Feb 07 '22 at 20:29

maraca · Accepted Answer · 2022-02-07T22:25:53.297

If you would only need the sum, then it could be solved in O(n). Because you need to print the sub-arrays this is not possible. But it also makes it pretty easy (I don't know C#, replace the print with what you need):

int total = 0;
for (int start = 0; start < n; start++) {
    for (int end = start + 1; end <= n; end++) {
        int max = arr[start];
        print(arr[start]);
        for (int i = start + 1; i < end; i++) {
            print(", " + arr[i]);
            if (arr[i] > max)
                max = arr[i];
        }
        total += max;
        print("\n");
    }
    print("\n");
}
print(total); // or whatever you want to do with it

This avoids the last comma, but you can switch it back if you want to. Also readable variable names can be helpful.

end is not inclusive, I prefer it that way because then you could get the length of the sub-array with end - start. E.g. Java's substring works exactly the same.

printing subarray is only for representational purposes, If you have a better-optimized solution please do also post for others. — Aman Aggarwal, Feb 08 '22 at 07:53

Print all subarray of given array and than store maximum integer in each subarray to get the sum of all maximum's?

1 Answers1