<< problem 148 - Exploring Pascal's triangle | Searching a triangular array for a sub-triangle ... - problem 150 >> |
Problem 149: Searching for a maximum-sum subsequence
(see projecteuler.net/problem=149)
Looking at the table below, it is easy to verify that the maximum possible sum of adjacent numbers in any direction
(horizontal, vertical, diagonal or anti-diagonal) is 16 (= 8 + 7 + 1).
-2532
9-651
3273
-18-48
Now, let us repeat the search, but on a much larger scale:
First, generate four million pseudo-random numbers using a specific form of what is known as a "Lagged Fibonacci Generator":
For 1 <= k <= 55, s_k = [100003 - 200003k + 300007k^3] mod 1000000 - 500000.
For 56 <= k <= 4000000, s_k = [s_{k-24} + s_{k-55} + 1000000] mod 1000000 - 500000.
Thus, s_10 = -393027 and s_100 = 86613.
The terms of s are then arranged in a 2000x2000 table, using the first 2000 numbers to fill the first row (sequentially),
the next 2000 numbers to fill the second row, and so on.
Finally, find the greatest sum of (any number of) adjacent entries in any direction (horizontal, vertical, diagonal or anti-diagonal).
My Algorithm
The basic problem is known as "Kadane's algorithm", see here: en.wikipedia.org/wiki/Maximum subarray problem .
In one dimension it does the following:
1. assume that the first element is the best sum
2. add consecutive elements and check every time:
- does the current sum exceed the previously best sume ? if yes, replace it
- is the sum negative ? if yes, reset it to zero
All random numbers are generated by
fillLaggedFibonacciSequence
and stored in data
which is a one-dimensional array.index
converts a 2D coordinate to a unique 1D position inside data
.maxSum
implements Kadane's algorithm: it analyzed all elements from data[first]
to data[last]
that are increment
steps apart.- if
maxSum
should analyze all numbers of a row, thenincrement
is 1 - if
maxSum
should analyze all numbers of a column, thenincrement
is the matrix's width (size = 2000
). - if
maxSum
should analyze all numbers of a diagonal from the top-left to the bottom-right, thenincrement
is the matrix's width plus one - if
maxSum
should analyze all numbers of a diagonal from the top-right to the bottom-left, thenincrement
is the matrix's width minus one
Alternative Approaches
In comparison to other problems, this is a pretty memory-consuming solution.
When adding a bit of extra logic you don't need to store the whole matrix - just the current row is enough if you update your sums accordingly.
Note
You don't need to scan the diagonals because they don't contain the maximum sum in this particular case ...
I used a bit of weird pointer arithmetic in fillLaggedFibonacciSequence
. It's been a long times since I needed negative indices !
Interactive test
This feature is not available for the current problem.
My code
… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.
#include <iostream>
#include <vector>
// 2000x2000 matrix
const size_t size = 2000;
int* data = NULL;
// find maximum sum of all elements from data[first] to data[last]
int maxSum(size_t first, size_t last, size_t increment)
{
// Kadane's algorithm
// https://en.wikipedia.org/wiki/Maximum_subarray_problem
int result = data[first];
int currentSum = 0;
for (auto i = first; i <= last; i += increment)
{
// "extend" current sum
currentSum += data[i];
// if sum is negative then there must be single element bigger or equal
// which is already stored in result
if (currentSum < 0)
currentSum = 0;
// improved sum ?
if (result < currentSum)
result = currentSum;
}
return result;
}
// fill 2000x2000 matrix
void fillLaggedFibonacciSequence()
{
// fill elements in consecutive order
int *current = data;
// initial 55 elements
long long k = 1; // note: if only int is used, then k*k*k overflows !
while (k <= 55)
{
*current++ = ((100003 - 200003 * k + 300007 * k*k*k) % 1000000) - 500000;
k++;
}
// ... to infinity and beyond !
while (current < data + size*size)
*current++ = ((current[-24] + current[-55] + 1000000) % 1000000) - 500000;
}
// convert 2D coordinate to a linear 1D coordinate
size_t index(size_t x, size_t y)
{
return y * size + x;
}
int main()
{
// allocate memory
data = new int[size*size];
// generate sequence
fillLaggedFibonacciSequence();
auto last = size - 1;
auto result = data[0];
// horizontal
for (size_t y = 0; y <= last; y++)
{
auto current = maxSum(index(0, y), index(last, y), 1);
if (result < current)
result = current;
}
// vertical
for (size_t x = 0; x <= last; x++)
{
auto current = maxSum(index(x, 0), index(x, last), size);
if (result < current)
result = current;
}
// diagonal \ => from upper to right edge
for (size_t x = 0; x <= last; x++)
{
auto current = maxSum(index(x, 0), index(last, last - x), size + 1);
if (result < current)
result = current;
}
// diagonal \ => from left to lower edge
for (size_t y = 1; y <= last; y++) // y = 0 was already checked by previous loop
{
auto current = maxSum(index(0, y), index(y, last), size + 1);
if (result < current)
result = current;
}
// diagonal / => from upper to left edge
for (size_t x = 0; x <= last; x++)
{
auto current = maxSum(index(x, 0), index(0, x), size - 1);
if (result < current)
result = current;
}
// diagonal / => from right to lower edge
for (size_t y = 1; y <= last; y++) // y = 0 was already checked by previous loop
{
auto current = maxSum(index(last, y), index(y, last), size - 1);
if (result < current)
result = current;
}
std::cout << result << std::endl;
delete[] data;
return 0;
}
This solution contains 18 empty lines, 21 comments and 2 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 0.07 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
Peak memory usage was about 18 MByte.
(compiled for x86_64 / Linux, GCC flags: -O3 -march=native -fno-exceptions -fno-rtti -std=gnu++11 -DORIGINAL
)
See here for a comparison of all solutions.
Note: interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without -DORIGINAL
.
Changelog
May 25, 2017 submitted solution
May 25, 2017 added comments
Difficulty
Project Euler ranks this problem at 50% (out of 100%).
Links
projecteuler.net/thread=149 - the best forum on the subject (note: you have to submit the correct solution first)
Java github.com/nayuki/Project-Euler-solutions/blob/master/java/p149.java (written by Nayuki)
Those links are just an unordered selection of source code I found with a semi-automatic search script on Google/Bing/GitHub/whatever.
You will probably stumble upon better solutions when searching on your own. Maybe not all linked resources produce the correct result and/or exceed time/memory limits.
Heatmap
Please click on a problem's number to open my solution to that problem:
green | solutions solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too | |
yellow | solutions score less than 100% at Hackerrank (but still solve the original problem easily) | |
gray | problems are already solved but I haven't published my solution yet | |
blue | solutions are relevant for Project Euler only: there wasn't a Hackerrank version of it (at the time I solved it) or it differed too much | |
orange | problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte | |
red | problems are not solved yet but I wrote a simulation to approximate the result or verified at least the given example - usually I sketched a few ideas, too | |
black | problems are solved but access to the solution is blocked for a few days until a new problem is published | |
the flashing problem is the one I solved most recently |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |
76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |
126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |
151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |
176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |
201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |
226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |
251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |
276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |
301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |
326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |
351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |
376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |
401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |
426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |
451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |
476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |
501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |
526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |
551 | 552 | 553 | 554 | 555 | 556 | 557 | 558 | 559 | 560 | 561 | 562 | 563 | 564 | 565 | 566 | 567 | 568 | 569 | 570 | 571 | 572 | 573 | 574 | 575 |
576 | 577 | 578 | 579 | 580 | 581 | 582 | 583 | 584 | 585 | 586 | 587 | 588 | 589 | 590 | 591 | 592 | 593 | 594 | 595 | 596 | 597 | 598 | 599 | 600 |
601 | 602 | 603 | 604 | 605 | 606 | 607 | 608 | 609 | 610 | 611 |
I scored 13,486 points (out of 15700 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.
My username at Project Euler is stephanbrumme while it's stbrumme at Hackerrank.
Look at my progress and performance pages to get more details.
Copyright
I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.
All of my solutions can be used for any purpose and I am in no way liable for any damages caused.
You can even remove my name and claim it's yours. But then you shall burn in hell.
The problems and most of the problems' images were created by Project Euler.
Thanks for all their endless effort !!!
<< problem 148 - Exploring Pascal's triangle | Searching a triangular array for a sub-triangle ... - problem 150 >> |