Print all subarray of given array and than store maximum integer in each subarray to get the sum of-CodePudding

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>();

CodePudding user response：

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.