Friday, October 28, 2022

There are heights for bars from a bar-chart provided. Find the maximum area of a contiguous rectangle bounded by the bar chart in a streaming manner where the bars appear to the right along the x-axis.
public void getMaxRectangleByStream(List<int> A, List<int> sums, int current)
{
   for (int i = 0; i < sums.size(); i++)
   {
        for (j = i; j < sums.size(); j++)
        {
if (A[j] <= current && sums[j] >= A[j] * (sums.size()-j))
        {
              sums[j] += A[j];
        }
                break;
        }
   }

   int sum = current;
   for (int j = sums.size() - 1; j >= 0; j--)
   {
       if (A[j] >= current)
       {
          sum += current;
       }
       else
       {
         break;
       }
   }

   sums.Add(sum);
}

class Solution {
    public int solution(List<int> A) {
        var sums = new List<int>();
        for (int i = 0; i < A.length(); i++)
        {
getMaxRectangleByStream(A, sums, A[i]);
        }

        return sums.stream().max();
}

            

A:            4, 6, 2, 4, 12, 7, 4, 2, 2, 2

sums:    8, 6, 20, 16, 12, 14, 16, 20, 20, 20


No comments:

Post a Comment