Biggest Rectangle Algorithmus für zweidimensionales Array - Problem

[Hikaruchan]

Mittlerweile find ich zwar immer ein Rectangle nur ist es nicht immer das größte, obwohl es das größte sein müsste nach dem obrigen Algorithmus (siehe Link)

Scheinbar implementiere ich den Algorithmus nicht 100%ig richtig, ich seh aber nicht was ich falsch mache.

hier mal aktueller Code:

#include <iostream>
#include <ctime>
#include <vector>

using namespace std;

int mapsize = 10;

void init(char** map){

	srand(time(0));



	for(int i = 0; i<mapsize; ++i){
		cout<<"\n";
		for(int j = 0; j<mapsize; ++j){
			//map[i][j] = '1';
			map[i][j] = (char)((int)(rand()/(double)(RAND_MAX)+0.1)+'0');
		}
	}
	//map[9][10] = '1';
	//map[9][11] = '1';
	//map[10][9] = '1';
	//map[10][10] = '1';
	//map[10][11] = '1';
	//map[10][9] = '1';
	//map[11][9] = '1';
	//map[10][8] = '1';
	//map[11][8] = '1';
	//map[11][10] = '1';
	//map[11][11] = '1';
	//map[11][12] = '1';
	//map[12][10] = '1';
	//map[12][9] = '1';


	for(int i = 0; i<mapsize; ++i){
		cout<<"\n";
		for(int j = 0; j<mapsize; ++j){
			cout<<map[i][j];
		}
	}
	cout<<"\n\n";

}

struct Pos{
	int x;
	int y;

	Pos(){
		x = 0;
		y = 0;
	}

	Pos(int x, int y){
		this->x = x;
		this->y = y;
	}
};

struct Rectangle{

	Pos ur;
	Pos ll;

	Rectangle(){
		ur = Pos(-1,-1);
		ll = Pos(0,0);
	}

	Rectangle(Pos ur, Pos ll){
		this->ur = ur;
		this->ll = ll;
	}

};

struct TempRect{

	int startPos;
	int width;

	TempRect(int startPos, int width){
		this->startPos = startPos;
		this->width = width;
	}

};

int area(Rectangle best_rect){


	if (best_rect.ll.x > best_rect.ur.x || best_rect.ll.y > best_rect.ur.y){ // If ur is left of or 
		return 0;               // below 11: return 0 
	}
	else{

		int val = (best_rect.ur.x-best_rect.ll.x+1)*(best_rect.ur.y-best_rect.ll.y+1);

		return val;
	}

}

void update_cache(int x, char** map, int* cache){

	for(int y = 0; y < mapsize; y++){
		if(map[x][y] != '0'){
			cache[y] = cache[y]+1;
		}else{
			cache[y] = 0;
		}
	}

}

void findBiggestRectangle(char** map){

	int* cache = new int[mapsize];
	vector<TempRect> rectangle_stack;
	Rectangle best_rect;
	TempRect oldRect(0,0);

	for(int i = 0; i < mapsize; i++){
		cache[i] = 0;
	}

	int width = 0;

	for(int x = mapsize-1; x >= 0; x--){
		update_cache(x, map, cache);
		width = 0;
		for(int y = 0; y < mapsize; ++y){
			if(cache[y] > width){
				rectangle_stack.push_back(TempRect(y, width));
				width = cache[y];
			} else if(cache[y] < width){
				do{
					//cout<<rectangle_stack.size();
					oldRect = TempRect(rectangle_stack.back().startPos, rectangle_stack.back().width);
					//oldRect = rectangle_stack.back();

					
					rectangle_stack.pop_back();

					if(width*(y-oldRect.startPos) > area(best_rect)){
						best_rect.ll = Pos(x, oldRect.startPos);
						best_rect.ur = Pos(x + width-1, y-1);
					}
					width = oldRect.width;

				}while(cache[y] >= width && rectangle_stack.size() != 0);
				width = cache[y];

				if(width !=0){
					rectangle_stack.push_back(TempRect(oldRect.startPos, width));
				}
			}
		}
	}

	cout<<"ll x: "<<best_rect.ll.x<<" ll y: "<<best_rect.ll.y<<endl;
	cout<<"ur x: "<<best_rect.ur.x<<" ur y: "<<best_rect.ur.y<<endl;
	for(int j = best_rect.ll.y; j <= best_rect.ur.y; ++j){
		for(int i = best_rect.ll.x; i <= best_rect.ur.x; ++i){
		
			map[i][j] = 'x';
		}
	}

	for(int i = 0; i<mapsize; ++i){
		cout<<"\n";
		for(int j = 0; j<mapsize; ++j){
			cout<<map[i][j];
		}
	}
	cout<<"\n\n";

}


int main(void){



	char** map = new char*[mapsize];

	for(int i = 0; i < mapsize; ++i) {
		map[i] = new char[mapsize];
	}

	for(int i = 0; i<mapsize; ++i){
		//cout<<"\n";
		for(int j = 0; j<mapsize; ++j){
			map[i][j] = '0';
			//cout<<map[i][j];
		}
	}
	//cout<<"\n\n";

	init(map);

	findBiggestRectangle(map);


	return 0;
}

Sieht jemadn was ich anders oder falsch implementiert habe bei dem Algo?