r.ramkumar
BAN USERWe should pass -1, as initial MaxHeight
int _tmain(int argc, _TCHAR* argv[])
{
vector<int> Histogram;
Histogram.push_back(22);
Histogram.push_back(22);
Histogram.push_back(6);
Histogram.push_back(6);
Histogram.push_back(6);
Histogram.push_back(6);
Histogram.push_back(6);
int sum = MaxRectangleAreaHistogram(Histogram, 0 , 1, -1);
cout << "Sum is " << sum;
getchar();
return 0;
}
Working C++ code:
int MaxRectangleAreaHistogram(vector <int> HistogramVec, unsigned int length, int width, int MaxHeight)
{
if (length >= HistogramVec.size()) // processed all histograms
{
return 0;
}
int HistHeight = HistogramVec[length];
if (MaxHeight > HistHeight) //prev recursive call does not apply to this
{
return 0;
}
int sum = 0;
int maxSum = 0 ;
if (MaxHeight < 0 ) {
maxSum = HistogramVec[length];
sum = MaxRectangleAreaHistogram(HistogramVec, length + 1, width, -1);
if (sum > maxSum) {
maxSum = sum;
}
for (int i=0; i <HistHeight ;i++)
{
sum = (i+1)*width + MaxRectangleAreaHistogram(HistogramVec, length + 1, width, i+1);
if (sum > maxSum) {
maxSum = sum;
}
}
}
else
{
sum = MaxHeight + MaxRectangleAreaHistogram(HistogramVec, length + 1, width, MaxHeight);
if (sum > maxSum) {
maxSum = sum;
}
}
return maxSum;
}
We should pass -1, as initial MaxHeight
- r.ramkumar November 20, 2010int _tmain(int argc, _TCHAR* argv[])
{
vector<int> Histogram;
Histogram.push_back(22);
Histogram.push_back(22);
Histogram.push_back(6);
Histogram.push_back(6);
Histogram.push_back(6);
Histogram.push_back(6);
Histogram.push_back(6);
int sum = MaxRectangleAreaHistogram(Histogram, 0 , 1, -1);
cout << "Sum is " << sum;
getchar();
return 0;
}