Suppose you are a real estate developer. These days, the market is getting tight so you have decided to turn to algorithms to give you an edge over the competition. You have purchased an irregularly shaped plot of land which you have divided into a square grid. For each square, you have calculated a cost. For example, building where the ground is less stable will cost you more. However, building on a square also has some value to you. For full generality, each square could have its own value as well. For example, a square overlooking the sea might be great to build on. As a simplifying assumption, you’ve decided that the value of a house is the value of the sum of its squares.
You wish to build a rectangular house with the greatest net value (value - cost). How can you do this efficiently? Here’s an example where we’ve pre-combined cost and value:
| -9 | 3 | -9 | 6 | 8 | 6 | 0 | -8 | -1 | -6 | -7 | 8 | |||
| 5 | -8 | -8 | 4 | -6 | 0 | 5 | 3 | 5 | -3 | -5 | -4 | -10 | 6 | -2 |
| -1 | 9 | -6 | -2 | -10 | -6 | 5 | -7 | -1 | -8 | 0 | -10 | -4 | 9 | -2 |
| 6 | -7 | 10 | -5 | 4 | 4 | -7 | -2 | -6 | 4 | -5 | -3 | 10 | 10 | 7 |
| -1 | -3 | 1 | 7 | 6 | 2 | 3 | -5 | 7 | -6 | 5 | 2 | 4 | -4 | 2 |
| -5 | 10 | -7 | -3 | 7 | 4 | -4 | 1 | 1 | -5 | 5 | -8 | -9 | 0 | -9 |
| -3 | -8 | -8 | 1 | -5 | -4 | 6 | 2 | 0 | -3 | 8 | 6 | -5 | -7 | 6 |
| 2 | -3 | -3 | 9 | 9 | 10 | 4 | 7 | -5 | 8 | 4 | 2 | 7 | -6 | 10 |
| -8 | -1 | 9 | 2 | -8 | 4 | -1 | 9 | 3 | -6 | 4 | -9 | 0 | ||
| 5 | -9 | -4 | -5 | 6 | 7 | -5 | -9 | 5 | -1 | 5 | 1 | 4 | -6 | 4 |
| 3 | -6 | 5 | 3 | 6 | -8 | -8 | -9 | -10 | -10 | -10 | -9 | -4 | 8 | 9 |
| 8 | 1 | 3 | 4 | 10 | 3 | 0 | 8 | 0 | 4 | 6 | -2 | -3 | 4 | -5 |
| -6 | -1 | 0 | 4 | -2 | -6 | 7 | -7 | 1 | -2 | -10 | 4 | -4 | 0 | -5 |
| -8 | -5 | 5 | -8 | 2 | 4 | 9 | 8 | -4 | -6 | 10 | -7 | -6 | ||
| 10 | -6 | -10 | 5 | -1 | 4 | -4 | 10 | 1 | -1 | -3 | -9 | 7 |
The max sum is highlighted and it’s 86.
Think for a few minutes before reading below…
We don’t consider the cost and value separately because they are inseparable; we only consider each square to have a net value. First, it seems like we want to “flatten” this irregular array into a rectangular array containing net values (similar to a 2D image operation). To do this, we can determine what is the maximum possible value any rectangle could have by adding all the positive net values, add 1 to make a value BIGGER than any possible rectangle, then negate. When we flatten the array to the smallest bounding rectangle, we can fill in the empty squares with this value, which we know we will never incorporate.
After that, if the bounding rectangle is n × m, exhaustive search leaves us with an n3m3 solution, which is quite slow. To see this, we pick an upper-left coordinate (n × m), a lower-right coordinate (n × m), and then visit all the entries of this selected rectangle to sum them (n × m once more) which has the product given.
Here’s an implementation written in Java. ar is the input array. coords is a 2 by 2 array used to store the two corners of the optimal rectangle. The return value is the sum of the optimal rectangle.
public static int maxArraySumExhaustive(int[][] ar,
int[][] coords) {
int bestSum = 0; // The do-nothing sum
for (int i = 0; i < ar.length; i++) {
for (int j = 0; j < ar[0].length; j++) {
// (i, j) are our first two coordinates
for (int k = i; k < ar.length; k++) {
for (int l = j; l < ar[0].length; l++) {
// (k, l) are our second two coordinates
// Perform the sum
int sum = 0;
for (int y = i; y <= k; y++) {
for (int x = j; x <= l; x++) {
sum += ar[y][x];
}
}
if (sum > bestSum) {
bestSum = sum;
if (coords != null) {
coords[0][0] = i;
coords[0][1] = j;
coords[1][0] = k;
coords[1][1] = l;
}
}
}
}
}
}
return bestSum;
}
How can we improve upon this? There are several techniques to building an efficient algorithm. One is: simplify the problem. We’re dealing with an optimization problem in two spatial dimensions. What if we simplify to one dimension? That is, given a sequence of numbers, find the maximum contiguous subsequence sum. This problem is also known as “maximum sub-array sum”. It’s also a common interview question. A simple solution to this one takes O(n3) time. Pick all possible pairs for the ends; for each pair, sum the elements in the middle. We can drop an n factor with the following observation: we can build the sums as we go along rather than rebuilding them for each pair. In other words, start the left end at a fixed point, and grow the right end outward. Each element we grow rightward only takes constant work to add to the existing sum, but represents a new subsequence. This reduces the problem to O(n2) work.
But we can do even better using Kadane’s algorithm. We start by making a few observations. First, if all the numbers were positive, this problem would be easy: just include all the numbers. We also see that there is no reason why a sum should start with a negative number (if we allow empty sums). Let’s say we start summing at some point and keep extending to the right. Take a look at your partial sum. If it ever becomes negative, that partial sum is completely useless and we should throw it out and start over. On the other hand, as long as it’s positive, it makes sense to keep it around and add it to the next guy over. Finally, we would want to keep the best partial sum we can find. We can combine these observations into an O(n) algorithm:
public static int kadane(int[] ar, int[] se) {
// se stands for "start, end"
int accum = 0; // The do-nothing sum
int bestaccum = 0;
int bestStart = 0, start = 0, bestEnd = 0;
for (int i = 0; i < ar.length; i++) {
accum += ar[i];
if (accum < 0) {
// Reset
accum = 0;
start = i+1;
} else if (accum > bestaccum) {
bestaccum = accum;
bestStart = start;
bestEnd = i;
}
}
if (se != null) {
se[0] = bestStart;
se[1] = bestEnd;
}
return bestaccum;
}
After trying it out, you will find that this algorithm works. But our observations don’t really constitute a proof. In some circumstances, you might accept it anyway. If you invent a very complicated algorithm that seems to work well for fairly small instances, you still have reason to suspect it. But when you have a fairly simple algorithm that works for everything you can throw at it, the algorithm is probably correct.
Still, “probably” isn’t good enough for us. To prove that it works, we show that at the start of each iteration of the for loop, the prefix we are considering (”our” prefix) is the best possible one ending at that point. Suppose there is a better prefix. It could either be longer or shorter. If the “better” prefix is longer, the extra piece would have a positive value over our prefix, which is a contradiction, because our algorithm never throws away a positive value prefix. If the “better” prefix is shorter, the missing piece in our prefix must still have a positive value, again because otherwise we would have thrown it away. This is a contradiction: the shorter piece could have included it for a better value. Therefore, we must have the best prefix. And of course, the optimal subarray is an optimal prefix ending at some point, and we will remember the best prefix we see at all points.
Now, how do we extend this to two dimensions? It would be hard to believe that a Kadane-like insight holds true for two dimensions. But we can use the O(n2) technique to boost Kadane’s algorithm. We use the O(n2) technique to consider all possible consecutive runs of rows. When we consider a run of rows, we will have summed the columns into a single row, and at that point we can apply Kadane. (We can’t just do a simple 2D extension of Kadane because holding onto a row can “drag us down” even though we stay positive with it. Even in the array [[1, -1000], [-1000, 1000]], we will insist on holding onto the first row with double Kadane because the 1 is positive, even though we should ditch it so we can get the positive 1000 value.)
Together, these techniques solve the problem in O(nm2) time, where m is the smaller dimension. Here’s the Java code:
public static int maxArraySumFaster(int[][] ar,
int coords[][]) {
int[] partialSum = new int[ar[0].length];
int maxSum = 0;
int[] miniCoords = new int[2];
for (int i = 0; i < ar.length; i++) {
Arrays.fill(partialSum, 0);
for (int j = i; j < ar.length; j++) {
// partialSum is sum of rows from i to j
for (int k = 0; k < partialSum.length; k++) {
partialSum[k] += ar[j][k];
}
int sum = kadane(partialSum, miniCoords);
if (sum > maxSum) {
maxSum = sum;
if (coords != null) {
coords[0][0] = i;
coords[0][1] = miniCoords[0];
coords[1][0] = j;
coords[1][1] = miniCoords[1];
}
}
}
}
return maxSum;
}
We assume that the vertical dimension is smaller; if it’s not, it should be obvious how to “rotate” the algorithm. Let’s say we divided our land into a 50 by 50 array. Benchmarking the Java solutions, the faster solution is 2000 times faster; the slow solution takes about 2.8 seconds on my machine, but the fast solution takes only 1.4 milliseconds. For a 60 by 60 array, the slow solution take 8 seconds (2.8 times slower than before), but the fast solution takes 2.3 milliseconds (1.6 times slower). The gap will only continue to widen for larger arrays.
There is another nice solution that is considerably faster than brute force (but slower than your algorithm), coming in at O(m^2 n^2) as follows.
We first will build an O(mn) sized data structure. For each point (i, j), we will compute the sum of the items from the origin to i, j. We could do this in O(mn) time with dynamic programming, but the naive just add them all solution won’t make our implementation asymptotically slower, because the next step in our algorithm will eat all of our running time.
Now, for an arbitrary rectangle, we can calculate its sum in O(1) time with some clever inclusion-exclusion with our prebuilt data structure.
sum(x1, y1, x2, y2) = sum(0, 0, x2, y2) - sum(0, 0, x1 - 1, y2) - sum(0,0, x2, y1 - 1) + sum(0, 0, x1 - 1, y1 - 1)
Note that all of the sums involving 0,0 are pre-computed. Note that there are special cases when you are on the edges, but we’ll ignore them as implementation details.
So then, with our handy insight, we can enumerate each rectangle by enumerating opposite corners, and then calculate the sum for each rectangle.
As someone who has been involved in real estate development for over five years, I can tell you that there are far greater factors of importance than the exact location on the land grid of where the building should be located.
Time to build, cost of labor, cost of financing, time to sell, all of those are much more important that the exact grid orientation of the building. Some factors can be reduced to cost/value numbers to put in the grid, but may factors are external and have no effect. In addition, the exact physical location of the building will be determined by things such as drainage, setbacks, vehicle and pedestrian access, wind orientation, and view orientation, among others.
Ian:
It’s great to hear from someone with actual experience in this domain! I have no doubt that you’re right. This was a bit of a contrived example. But I thought it was fun to create a solution for this problem. And I still think that it could give you a starting point for selecting a building site if you believe that the factors covered by this model are among the most important ones for a given scenario. Still, this algorithm is never going to put someone like you out of a job.
Hello!
I found this from reddit. That was a great refresher on Kadane’s Algorithm, and it was useful to see it in the context of another algorithm. Thanks!
Your algorithm posts have been really exciting to read. Great work. I hope you post a new article soon.
Great site!
46cef765971334edf2f4…
46cef7659713…
elavil facts…
news…
alprazolam south america…
news…
carisoprodol phentermine yellow…
news…
azaxswhr…
azaxswhr…
Pay Day Loans No Fax…
We think that because financial controllers from Charleston recurrently propose payday loans…
adderall side effects…
news…
buy vicodin…
news…
hi…
agree…
lorazepam side effects…
news…
Sony Introduces the Full HD…
Sony Electronics Asia Pacific introduces its latest SXRD Home Theatre Projector VPL-VW200. This new 1920 X 1080p projector is power-packed…
Flip this house: ‘We’re bringing…
“Like the master bedroom bathroom had no outlet. I would flip out if I bought a house with no bathroom…
Principal extraordinaire : Joyce Dwyer…
Students sealed a 2007 time capsule while unearthing one dating to 1956, complete with student and teacher signatures, a mid-century…
Zillow.com(R) Launches Dynamic Real Estate…
Zillow(R) Smart Search Helps Users Find Real Estate Information Most Relevant to Them; Enhanced Neighborhood Pages Provide In-Depth Views…
Effort to Broaden Cyberspace Community…
Microsoft’s software will be used to support the leading digital empowerment organization’s core service modules. In addition, HOPE’s corporate ……
Posted Dec. 7, 2007 -…
Dollar, pastor of World Changers Church International in College Park, Ga., is one of six TV preachers who were asked…
OurChurch.Com Launches NE1™ Website Builder…
Tampa, FL, January 04, 2008 –(PR.com)– OurChurch.Com, a leading provider of web hosting, design, marketing, and advertising services to Christian…
BUYINS.NET: NIS, SIG, BJGP, BWLD,…
The company also engages in land development and conversion of existing rental apartment communities to condominiums. In addition, it offers…
Home-design community unites under new…
The center also is the new home of the American Society of Interior Designers, Texas Gulf Coast Chapter, an organization…
Wrestlers weigh in after the…
With Joe Locksmith winning the 125-pound weight class, Dr. Phillips placed fifth of 27 teams in last weekend’s King of…
VAI to Host Series of…
Implementing an advanced Warehouse Management Solution (WMS) can provide several business benefits including overhead cost reductions, warehouse space ……
VIRGINIA: Pat Robertson contemplates bid…
It is parent to nine daily papers and more than 100 nondaily newspapers and specialty publications. Landmark also owns…
Social Sins,’ binoculars, Mozart -…
… presented Bush with a portrait of the US president made with rubies and various gemstones, held in an ornate…
lgasxebc…
lgasxebc…
Continuation of the series on…
Do not run behind kitchen units or allow the hose to come into contact with the hot part of any…
Cash Advance…
If you are small on dollar just effortlessly sign up for an online online cash advance that is best, self-explanatory, and sudden today!…
Tokyo shares mixed on profit-taking…
The US Commerce Department said overnight that durable goods orders increased 5.2 percent in December, the largest rise in five…
Fast Break with Kittery Maine…
Fast Break with Kittery MaineLibertyFlames.com, VA -Jan 31, 20084×4 Ford or Chevy Truck What is your favorite season of the year? Spring…
Bonbons beckon as Wine Country…
Bonbons beckon as Wine Country greets cupid this weekendSanta Rosa Press Democrat, CA -30 minutes agoAnd I donât play favorites. I like…
Sport Clips Marks 500th Store…
Sport Clips Marks 500th Store OpeningFranchise Wire (press release), New Zealand -Jan 23, 2008âThis resonates with men and boys who donât look…
AeronautX Appoints New International Marketing…
AeronautX Appoints New International Marketing ManagerPR-USA.net (press release), Bulgaria -28 minutes agoAeronautX is an FAA Approved Part 141 School, VA Approved School,…
Formerly homeless, rookie jockey finds…
Edward Sr. helped her move to Virginia with Toshi, and she wound up spending three months at Western State Hospital,…
Retail Sales Surprise to Upside…
Retail Sales Surprise to UpsideTheStreet.com -50 minutes agoSales slid by 1.0% at electronics and appliance stores. Stocks rallied on the retail…
HOMEX Launches a New Division…
HOMEX Launches a New Division to Serve Second-Home Market in …StreetInsider.com (subscription), MI -14 hours ago”This shift in lifestyle, spurred by the…
Terrarium makes best home for…
Terrarium makes best home for colorful nerve plantIndianapolis Star, United States -Feb 1, 2008These plants are often used as specimens among other…
Staging ‘Phantom’ an epic task…
Shaking hands fumble with buttons, tug uncooperative wigs and lace corsets. “Ya’ll, it’s 7:15. We’ll never make it!” Panicked voices…
Our favorites: Music - Marconews…
In that relatively brief time their orchestra has positioned themselves as a crown jewel, not just in Collier County,…
Three online finance applications to…
You have to read the fine print carefully on such offers to determine if they would really save you money….
Nanda grounded; questioned by CBI…
Nanda grounded; questioned by CBI for barak dealUdayavani, India -Jan 31, 2008… going in favour of PSP Bohemia of Czech Republic…
HVAC Air Purification Company Introduces…
HVAC Air Purification Company Introduces Nanotechnology Air Duct …Nanovip.com (press release), NY -Feb 3, 2008Every UV air purifier is shipped with a…
Gong Xi Fa Cai at…
eTravelBlackboard - Asia EditionGong Xi Fa Cai at Orchard Hotel SingaporeeTravelBlackboard - Asia Edition, Australia -Jan 21, 2008Begin the celebrations with a…
Gregory…
…Consider a cheap air purifier, these are both helpful and healthy for any person living or visiting your household……
tampa condominiums…
Interestingly, this was on CNN last week….
Web Development Search Optimization Ny…
Want to take a look at my web site, you will find it very interesting….
Angie…
…
Jacky…
…
How To Build Home Theater Projector…
Our lives begin to end the day we become silent about things that matter. ~ Martin Luther King, Jr….
Jessie…
…
AdSense Money Maker…
Do you know how to make money from AdSense automatically? You don’t!? I’ll teach you how!…
Cash Payday Loans Loans Dating…
Can it be that your server is infected with a virus - I get an Virus warning when I open your site with Firefox - Just for your Info….
Money Magazine New Construction Associated Press…
I didn’t agree with you first, but last paragraph makes sense for me…
Advanced Pilates…
I just can’t understand some parts of this article……
Software Software Test Discount Software…
I didn’t agree with you first, but last paragraph makes sense for me…
hvac business software…
…
Wedding Rings Class Rings Pearl Harbor…
I didn’t agree with you first, but last paragraph makes sense for me…
adderall…
adderall generic amphetamine…
feed…
…
Real Estate House Of Representatives House Md…
I didn’t agree with you first, but last paragraph makes sense for me…
Jim Crow Laws Family Law Law School Rankings…
I didn’t agree with you first, but last paragraph makes sense for me…