Rain water harvesting question. What am I doing wrong in here?

#1

#include
#include
#include<bits/stdc++.h>
using namespace std;

int main()
{
int n,a[1000];
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}

int sum = 0;
int diff= 0;
int premax = INT_MIN;
int postmax = INT_MIN;

for(int i=1;i<n-1;i++)
{
    for(int j=0 ; j<i ; j++)
    {
        premax = max(a[j],premax);
    }
    
    for(int k=i+1 ; k<n ; k++)
    {
        postmax = max(a[k],postmax);
    }
    
    if(premax>=a[i] && postmax>=a[i])
    {
     if(premax>postmax)
     {
        diff = postmax-a[i];
        sum = sum + diff;  
     }
     else
     {
        diff = premax-a[i];
        sum = sum + diff; 
     }}
}

cout<< sum;
return 0;

}

#2

can you explain what you have done in your code? Like the algorithm and data structures used.
Then I can better explain the error

#3

To start with, I’m just finding the max Height on both the sides and then I am finding the minimum of the two max heights and adding its difference with the corresponding element to the final sum.

#4

A much better approach would be to create 2 arrays premax[] and postmax[] and store the corresponding amount for each element respectively. Will help save a lot of time wasted in the loop
Also
for(int j=0 ; j<i ; j++)
{
premax = max(a[j],premax);
}
This block of code will then become constant time as premax[i] = max(a[i],premax[i-1])
Similarly for postmax

#5

Yes I understand that, but what is wrong in this one? It is working but not giving the desired response.

#6

It is working but time consuming hence not giving the desired response. You are unnecessarily doing repetitive work