14 Dec, 2011, Idealiad wrote in the 1st comment:
Votes: 0
So I've been reading a book lately and I'm about halfway through it. The chapter I just started poses a small but interesting problem.

Given a vector of floating-point numbers, find the largest sum among the contiguous subvectors.

So for example, in the vector x

[45 -34 8 7 48 -30]

The contiguous subvector with the largest sum is x[2…4] totaling 63.

Now this problem would not be so interesting but for the story behind it. The author tells a story that the original algorithm the programmer came up with was going to take 15 days to process a vector of 100,000 numbers (note that this book is relatively old).

However, redesigning the algorithm brought the time down to 5 milliseconds.

So, your challenge, if you choose to accept it, is to try your hand at solving this problem.

At the end of this post you'll find a vector of 5000 random numbers to use. We can make it bigger if necessary.

Time your tests and post the results in the thread. Any language is acceptable. I encourage multiple attempts to make it faster. If you wish, refrain from reading the thread until you post your solution, but if you want to see other people's attempts first feel free.

Good luck!
Quote
[336 502 -557 -371 507 -199 665 -497 452 426 -56 -641 641 -284 603 -3 -445 -347 -531 -667 -403 -472 43 -348 -229 -235 -370 345 -563 578 109 49 -520 530 -612 -671 -69 -514 138 394 -367 164 -89 -445 221 -431 -571 -466 358 313 564 -203 13 474 -603 -264 -681 -229 481 412 488 490 -38 373 666 222 -101 -600 -259 -48 -86 -621 -169 -203 -166 442 43 517 -681 196 347 483 37 -376 -469 451 229 250 -675 -238 563 692 486 -42 281 -252 251 -322 -122 -140 -251 -267 -42 336 240 257 -301 -5 423 609 690 -203 -114 253 541 10 -329 574 -250 -506 621 -224 -317 -389 -236 481 -364 97 -561 326 -95 -681 400 446 -118 -654 -285 587 18 -493 18 34 374 173 -394 666 -161 486 -656 -323 49 137 178 -98 -627 -438 485 -315 -97 148 -343 -73 411 318 -687 668 154 646 576 -102 -297 541 571 379 -71 -75 -5 409 328 -338 660 -84 407 152 197 613 607 -201 -88 -405 131 675 -546 -647 176 349 567 621 -262 332 -403 -52 623 465 -464 -82 525 352 591 -210 62 352 -351 -646 -554 159 -467 -66 -248 467 -60 668 396 70 672 -371 -561 -570 -212 496 673 -182 -19 25 -231 -348 -156 233 642 -19 171 237 23 -258 379 -600 110 665 266 -87 -265 143 619 267 653 646 -21 604 449 173 363 482 184 -613 487 245 52 -248 -638 569 126 364 689 -291 250 -333 485 -32 337 468 -305 -242 -545 -658 338 -612 341 436 -337 340 477 -42 75 262 -208 -81 28 369 -464 -386 -474 375 34 -237 154 -4 19 -194 -48 -24 483 359 474 -330 691 -553 187 -659 -522 385 59 601 -90 151 61 615 416 -184 164 -385 -434 651 551 74 -520 -454 -191 -440 479 -396 31 -47 429 515 -392 574 -571 -585 -580 -601 226 353 462 437 -182 461 444 -105 686 -255 -671 -105 -168 88 -425 -30 681 -491 290 -87 -306 -530 27 262 539 699 652 425 -166 415 -527 -670 504 7 -609 624 148 416 -601 185 -252 358 121 -65 -256 603 -268 40 505 -80 448 -654 -448 117 207 311 -102 453 568 156 -113 215 -275 -629 70 -418 -694 -357 524 -540 -408 492 348 89 -631 322 120 155 -16 235 -19 109 319 -272 470 207 465 222 683 -699 -120 -355 -156 -157 458 -676 47 -62 492 249 41 -532 90 438 -555 -170 8 -650 -663 653 612 -576 531 14 460 686 -504 -75 -269 -597 -367 435 -505 29 -390 612 -543 -232 -318 -613 -604 429 368 168 68 -118 -49 -547 699 -35 610 -456 -359 347 284 80 77 -456 -392 -220 605 16 -608 427 -481 -297 -409 -249 77 245 71 -142 205 34 -360 -194 104 -497 -249 585 535 376 560 -167 361 -458 598 -239 375 50 238 -459 -322 132 -475 -614 414 -385 555 431 634 586 -446 311 389 215 103 422 548 110 -460 -667 280 -379 -31 -31 -172 137 -118 -259 200 645 249 125 183 -263 697 299 27 627 -359 -510 62 -239 -179 -275 -518 123 -65 630 87 162 524 291 -675 -654 109 -133 445 -629 -261 -652 -92 -121 588 364 -609 -397 -16 -447 343 -559 -495 125 29 309 -353 -372 -168 -614 -238 -56 488 521 665 364 189 -412 490 -591 -676 -492 -162 -62 24 258 -515 -132 -127 682 -624 382 36 -519 521 100 -270 9 45 228 -375 -244 688 399 -149 -616 -635 602 -462 -465 -32 -357 -453 -697 -24 365 658 -633 339 -592 118 -227 -321 -86 -175 -438 130 -539 538 -362 -369 345 -685 362 -1 -409 244 334 264 -427 -555 617 -99 213 1 -618 261 -568 383 -220 -560 -409 -460 -97 -52 394 573 -44 -394 -325 442 197 -126 205 396 -411 32 -292 371 -218 -2 559 -292 -566 -208 -166 -29 -337 647 -502 -69 381 320 151 80 -11 -260 -390 -332 454 113 113 3 -545 550 565 -509 -225 -145 -501 -494 -260 -71 421 115 97 -679 346 -178 134 -162 -320 -111 169 48 -381 296 -637 32 404 -490 171 562 -433 196 -637 253 -150 -72 224 570 534 98 -105 309 -428 223 -682 376 -504 270 690 -340 698 272 -19 -608 -457 -468 -292 443 -113 -370 185 -433 482 697 -200 677 57 -231 209 142 -533 -130 -640 -17 -88 -422 -77 60 -207 -148 -478 214 225 239 551 342 -129 -642 -34 207 -132 -224 -666 -590 421 -431 354 335 -444 571 -265 -349 79 47 -696 -605 -299 673 -216 -132 -436 -231 -164 365 -505 -161 -662 524 434 -699 -364 420 -114 383 -462 409 -174 -221 311 261 34 368 -252 283 490 464 -42 -544 -44 237 -408 -481 -283 654 3 668 -52 501 525 -299 392 -199 -22 -209 347 400 -94 429 -326 528 -366 357 507 533 -5 -682 -115 200 286 -105 90 322 -338 -331 -647 421 -33 -137 86 480 384 36 -9 331 -380 -79 550 -302 557 97 214 -607 -2 -639 398 -660 -229 282 -136 -325 165 -511 -383 -433 260 -188 -231 46 -277 -277 532 -26 -56 -472 -466 -259 42 360 71 -430 -14 413 -231 446 180 384 195 -273 597 558 561 -508 650 -285 245 -314 -494 -287 -640 5 236 -24 217 321 -521 -458 121 -468 -642 -351 181 -593 -294 282 618 619 40 76 437 -72 647 676 420 261 236 -693 672 -498 -226 -438 276 -578 488 -497 -563 -145 -623 -310 -303 509 37 271 -74 610 -87 558 264 -27 595 -556 506 -381 -680 135 -67 189 42 691 331 -53 -502 -573 138 302 81 -645 -188 -627 -66 -251 -612 -253 208 -403 565 -160 -44 388 -400 650 32 64 228 -294 553 18 672 435 -509 -276 655 -628 225 -594 -515 -11 -236 -587 -2 188 -312 260 513 -428 -454 244 80 -27 169 -564 598 390 202 -391 -72 320 -579 40 -218 529 194 -330 -442 -2 553 218 -484 -589 -340 -70 -602 -689 -575 -620 -234 374 390 -446 462 -545 -23 -567 -366 623 526 -422 638 136 324 -487 2 632 -169 -365 251 331 195 228 -210 11 242 407 371 281 -121 362 -262 687 144 569 161 -49 314 516 -48 438 -283 -185 -66 -528 -202 674 -628 684 -17 474 499 291 -508 213 440 195 -452 -126 -575 247 563 -616 142 263 -553 -326 33 -322 298 -310 -317 692 -213 696 -521 438 -275 -180 -104 -252 129 476 -257 -529 97 521 598 548 238 -418 -656 -653 458 -255 73 351 -561 128 40 137 74 -180 276 -352 -611 -309 698 -315 -445 107 343 476 -502 462 -248 7 -604 -4 -387 608 622 -86 -536 191 405 639 -402 193 216 -233 140 7 -81 -536 449 543 125 159 217 558 -655 -116 -354 414 232 -643 -242 53 615 -64 681 598 377 -287 -105 230 440 -570 -426 -377 165 -591 -492 -633 598 409 -186 -194 151 513 517 667 386 -382 -643 394 -517 -495 -658 -1 49 -298 -225 -568 -422 -181 -128 459 -235 -332 -685 -580 -452 -693 245 -649 533 102 -652 -89 133 613 157 484 -249 35 -609 454 -648 -11 -654 -547 -357 452 32 -244 -525 279 330 138 -693 139 -359 -116 -17 -117 -541 669 432 -336 129 607 -557 -625 -610 -45 -89 511 139 196 -310 -241 429 86 522 -260 76 273 -191 -190 -306 39 -648 685 -268 -583 389 475 510 -335 -562 696 -511 175 -351 86 160 -124 -577 -497 -508 26 -477 -344 -15 -166 -52 -694 194 672 266 564 406 201 557 -186 -266 111 -284 -358 264 -262 421 179 499 -13 578 549 -401 681 606 678 -373 -308 108 232 -181 433 -577 -312 279 675 -332 146 -539 468 -601 -533 138 -205 5 -86 -398 488 -324 540 3 -478 435 532 132 -11 -292 -84 -172 -504 546 418 -523 -577 -451 -4 478 -676 301 514 369 343 -179 -133 -498 698 235 -153 -86 317 -207 -539 -334 -216 -252 265 454 185 469 138 220 -424 115 464 364 -180 540 -37 692 681 615 334 -210 -231 -207 -60 185 291 137 -373 75 268 520 690 -203 -203 282 -134 67 -603 -84 -299 205 76 -614 -224 -351 660 229 605 67 152 -344 -102 -522 -587 -515 -398 662 606 345 431 85 -524 -329 -302 118 99 -208 533 -369 -638 -598 16 -87 206 -516 398 551 -222 409 -274 -695 655 179 592 -13 364 43 -92 -610 -428 -371 423 404 73 -304 134 -479 -186 29 -303 49 -183 579 667 -292 51 66 -269 649 3 -183 30 110 -104 530 -604 -29 356 -535 -293 -325 -457 191 11 688 -61 -124 136 378 525 -267 -88 -187 197 99 -510 511 -683 -74 360 -142 -418 -555 323 -585 314 326 -310 556 251 443 -3 517 348 -450 -363 152 -135 -71 697 -592 -95 56 75 -249 -455 -235 131 -598 -655 -16 -173 642 308 432 218 228 541 7 -399 -417 571 -16 -128 -406 665 554 -503 573 -392 527 -392 285 -141 142 544 385 91 461 -187 -64 51 330 -142 -463 288 -320 39 -180 133 325 529 262 424 103 -515 20 624 270 658 -184 -524 -69 -33 0 -525 282 314 225 249 -247 -557 -375 331 -510 -73 430 490 419 518 -611 -476 -440 -567 -676 151 -246 -508 -387 39 620 -5 170 367 570 407 -457 269 -137 -91 -478 426 -658 186 248 -677 5 -398 565 415 -121 540 217 641 -213 -442 265 467 -278 191 -238 -572 -580 16 -667 447 -391 -32 -653 -204 -171 213 -326 420 -346 -433 -51 642 518 618 290 174 -308 -489 618 29 -410 690 -61 216 522 235 401 678 -77 106 258 424 -183 -598 -154 -15 -446 497 -421 -179 -650 17 597 694 -599 549 -23 -340 -47 -698 252 322 -92 198 214 -411 -584 -345 498 352 -184 -281 369 -346 -278 518 -696 -190 -124 -89 286 -346 -195 -466 -541 666 43 173 -674 -395 -287 -595 177 -425 316 -254 189 585 -253 -507 542 -277 519 -283 -567 488 192 -369 81 465 456 106 606 5 -683 360 77 -302 89 -180 342 -670 -558 -647 61 -516 -130 194 -368 37 397 -134 -434 -267 -139 139 -158 -502 -218 -646 -71 371 -86 -688 630 29 96 84 438 -502 114 -419 -110 -102 -565 111 -485 -493 -271 46 140 -476 -357 -16 159 520 -542 -6 -479 -667 223 205 288 -484 144 141 464 -128 587 268 -587 370 -633 441 48 -271 388 -378 338 519 -562 -380 -202 -274 251 63 -686 -61 256 17 -202 -331 -547 309 510 166 243 385 570 95 -282 238 -220 -563 691 50 -102 355 -674 621 -511 -170 -106 55 -656 -605 462 -553 659 88 -646 -131 -426 -560 -98 276 -169 218 -79 502 562 -352 -476 -663 -657 -335 -165 546 -296 -471 42 -440 -599 -381 -288 261 504 401 443 580 101 322 -500 678 673 486 -49 -127 644 -623 323 80 105 396 225 -599 -144 184 -660 -376 228 -125 170 414 492 -495 -68 173 646 -389 306 -2 -606 -252 -435 -106 -489 651 537 -434 -563 -394 -21 464 -508 -49 -50 139 348 -301 101 575 -665 -160 400 -542 -577 -207 377 -292 -575 146 327 683 635 381 -289 -428 339 56 -155 60 -195 221 292 -399 -24 -5 -28 258 253 -415 -638 -420 -243 -497 -30 -92 533 -115 119 194 -678 42 438 -45 -618 -677 19 68 -402 209 -357 216 252 -219 322 81 346 -271 694 560 556 -341 435 71 560 -689 -613 250 226 160 -562 479 328 387 421 -12 348 -413 596 10 72 -68 -44 98 681 -471 362 -299 -503 -21 -433 527 367 -525 -171 422 -77 -463 554 -463 610 181 -639 514 -185 578 115 559 575 120 -8 -144 -249 92 -673 -241 164 180 525 -186 -559 -240 -579 63 205 495 437 -144 612 271 -205 -389 -419 456 643 383 -291 -349 300 -256 -409 33 448 -511 43 -685 -143 264 -514 312 282 -562 -408 68 14 41 92 -102 -533 435 -538 -432 -664 -443 568 151 -324 32 -264 312 -106 317 310 633 118 -451 -464 644 698 -113 -571 -644 -63 286 670 -153 -261 -54 453 -71 -60 -666 -578 282 -471 242 148 667 487 -516 203 -408 0 248 -192 401 423 -553 425 506 -24 616 600 314 46 297 -91 392 -82 355 -213 -448 -526 -327 506 -120 6 557 -122 -587 386 -347 174 454 589 490 -315 558 569 396 433 294 543 -520 389 461 362 -666 -637 -482 -578 -311 -491 445 -633 276 40 357 282 353 24 -421 25 242 418 -689 -16 169 81 19 -557 500 -690 66 -510 545 141 -578 -586 -440 693 -465 -482 344 -599 388 682 -483 -440 658 347 141 256 356 -353 -164 -138 -218 -453 -442 336 -133 684 -73 590 460 514 -430 678 457 639 -290 158 574 -557 -382 -340 161 665 578 -506 -494 277 421 180 -100 658 -577 -502 364 605 -144 64 333 336 356 -313 440 -169 177 -132 -35 279 256 643 -381 295 -404 -200 -460 463 -399 273 386 677 135 422 131 168 -188 -640 313 -97 535 -81 -85 -290 270 324 -645 417 599 445 -642 2 -298 69 47 209 -288 153 -532 -43 -538 -509 353 72 6 -265 -143 349 -692 636 457 -382 -246 -437 131 103 -465 -168 436 218 -368 563 -646 -539 137 -560 161 635 -355 549 124 356 88 -112 -458 10 -291 645 -291 -195 325 330 -149 29 26 -609 -238 417 363 70 540 -255 -63 138 204 250 -507 244 195 -527 -519 -217 -35 33 -689 508 -655 -353 625 150 343 -631 -6 212 -340 -524 -492 -403 -444 352 108 430 -100 321 611 418 -404 224 200 447 -447 -454 133 -159 556 480 -77 -244 -638 -180 568 116 -220 -509 385 -220 -635 -168 569 -142 -205 502 415 618 21 228 -343 -251 -315 274 -112 -294 488 -694 637 -248 619 480 -329 -89 -383 -79 -154 -624 -549 302 -292 -637 -534 -568 145 171 345 -333 -310 -574 -15 -690 431 476 -331 533 -291 -400 -408 -36 500 -126 -448 -583 9 429 2 246 434 -697 406 -204 -81 185 -680 541 -612 353 -96 -482 483 304 -551 -34 543 -623 -622 255 484 271 666 174 -674 -97 0 -509 319 63 282 682 -528 596 -666 325 -77 429 608 -508 516 -260 451 149 -333 77 599 -684 -86 509 -278 -107 -683 600 -534 304 236 628 215 40 41 602 438 -689 -266 -619 -345 189 -426 -364 -690 589 -302 76 -510 -99 -612 620 280 -269 -152 437 657 -268 273 664 46 -119 435 445 -60 621 -287 364 -56 466 39 595 653 331 -239 -121 -582 102 -61 -92 122 -56 -478 -516 10 210 -568 -687 330 -626 677 -618 543 -11 -342 226 -583 -655 -144 174 -345 -610 -647 83 -635 -392 237 -458 -472 -560 -79 -202 -441 -300 -136 604 -346 -325 -441 319 -530 276 -305 -298 319 -564 -194 4 -551 599 -23 57 -475 -208 341 -667 -525 18 506 -159 224 266 682 99 261 464 688 -669 -438 421 104 -170 98 -514 699 -111 73 650 542 60 503 -362 104 -135 -234 536 272 558 -183 455 -333 -431 631 -113 -681 175 -75 -434 -479 -347 -671 -494 264 243 -232 136 83 538 -650 429 -697 421 -492 202 183 -127 -567 -356 141 -382 353 547 -162 202 -452 -277 26 317 -512 539 545 -15 414 -221 -451 -614 128 534 -205 227 -89 -145 -678 355 -638 223 222 245 628 -314 -142 -584 399 -435 -34 513 -471 417 342 101 92 356 256 291 666 -563 -260 -223 -334 294 589 389 475 321 -360 672 269 -570 -190 689 -423 334 -110 224 262 -349 -141 -521 -533 -570 587 392 665 -299 -669 -132 403 458 602 -572 -492 -292 477 -99 80 558 17 416 -572 228 -615 445 661 517 68 670 299 109 664 493 96 -650 390 39 -263 422 171 528 -626 -518 -50 321 -588 390 81 691 -210 431 -171 567 238 -20 328 -282 496 636 74 200 -435 19 229 603 181 642 604 -274 -649 -614 -624 -501 -7 429 285 -388 -96 -335 424 352 157 -385 -42 -31 207 699 513 -148 -179 -336 68 -494 5 -367 648 -427 -410 102 -351 7 -155 95 217 -100 -335 543 341 642 -627 -653 -393 -623 -540 -534 190 -46 -20 350 -348 -69 -200 28 -419 536 406 219 467 -545 -261 451 -365 -223 539 -412 -309 -601 65 679 657 -102 174 -49 -82 -295 357 156 262 169 461 183 361 345 439 -388 370 -305 42 -418 413 -632 313 272 -46 -679 -524 -39 377 -501 463 318 -120 634 -662 504 639 504 327 -692 -245 -583 -606 -534 -166 -343 -10 -451 688 -276 -469 -278 444 359 689 411 101 103 -551 172 665 615 -553 -200 -113 148 -91 466 -614 -29 -641 338 -304 183 471 358 -419 -101 -610 -610 9 -218 643 -585 -290 288 -207 -669 -293 -587 -522 24 -626 -74 -466 -422 160 493 -86 -655 -8 389 105 -550 -637 -282 155 -227 560 518 -64 15 285 -86 -270 -290 -5 -669 -426 1 689 -87 346 -526 173 -23 583 632 -578 -655 -143 -55 113 -440 193 -632 -616 604 -392 430 -62 57 574 265 -330 221 -346 -208 -511 -239 592 -213 -105 319 491 -322 -225 315 686 230 -217 456 274 311 -567 -72 685 39 -38 181 -293 -463 -376 537 162 -8 569 148 -212 415 -646 615 -285 -557 153 -654 426 163 -452 -409 -503 -662 -513 -46 155 -328 -595 -404 -222 -673 -369 349 697 633 580 332 222 36 85 -170 194 -444 -510 -193 667 -32 191 420 -569 -309 -527 -269 -254 17 -430 105 -377 -666 -261 -485 -348 77 -391 47 514 152 24 167 -463 684 662 -166 53 -182 613 -646 128 376 -664 -491 -36 23 664 -556 -500 225 -511 638 -185 -238 -308 -286 -461 34 -252 -214 -76 -133 -277 517 -158 627 336 -490 -234 67 -323 119 431 -667 156 -692 685 567 -75 32 -586 253 -622 469 -130 -6 -611 -199 454 463 -610 -483 -280 -287 -77 402 -89 -575 241 63 307 -584 508 428 264 -315 136 690 665 -501 308 -648 594 -502 500 243 518 380 22 537 568 -320 -379 80 -338 -521 72 -382 298 -669 253 -76 221 -365 589 -252 681 665 603 194 -562 79 -200 -50 -485 -206 299 -519 548 -10 416 323 -533 585 78 -120 -421 -435 574 659 -626 -682 -242 -681 -143 -581 -483 237 -53 -290 633 551 -444 46 623 -170 -646 -425 439 568 -271 -190 -238 -297 -122 -272 -280 307 -108 219 -699 -570 569 -213 614 -493 -312 -243 -451 387 213 -88 -327 42 -413 434 -126 -422 -339 -44 -51 671 -425 -147 -652 303 392 114 -53 524 -333 147 -319 -184 518 282 61 -282 184 598 -243 -264 -4 -679 660 -381 -446 -60 388 6 -349 170 -323 213 -192 -44 -484 195 31 668 -310 -337 431 77 -606 501 -210 31 305 374 -374 -424 -350 584 24 504 523 610 247 -223 462 195 -26 130 -151 -685 -537 -476 -272 24 109 -406 159 -590 -84 348 381 -147 672 420 -350 -145 410 -429 -445 -614 375 219 74 95 -490 0 -122 -342 636 463 180 274 559 562 13 -246 -423 118 -245 -97 570 -574 -157 471 571 -221 522 -322 675 646 -633 467 508 93 -580 -126 566 642 -411 169 -308 324 556 366 137 249 407 510 -40 -302 496 -47 407 545 592 -143 -257 -418 -222 373 155 -632 -598 -603 472 -206 -72 -613 534 -175 -685 667 176 -476 -70 140 -479 503 608 557 651 -669 -678 694 103 419 -230 -251 -214 201 -569 110 -490 -363 147 -622 -59 644 -183 -279 -262 590 -564 92 -34 -687 206 264 464 9 165 -421 112 -330 232 156 -602 223 -250 295 204 -667 48 -584 211 432 -463 162 -51 -298 401 -362 681 349 -475 -466 -274 -629 -88 295 692 268 -277 620 -694 -102 228 214 -329 47 117 -488 -514 -113 -658 -81 200 145 -443 -498 -670 558 -13 611 123 171 101 -66 -339 -74 526 -273 -531 -191 -131 257 528 -600 -406 -208 639 -245 -219 549 -404 533 -57 -618 23 -521 -54 -534 19 613 53 178 -476 440 329 -628 670 490 -362 -218 -65 -499 256 16 453 335 431 31 -63 225 -326 604 -54 120 510 445 590 281 -173 506 -234 444 348 623 -27 -692 293 540 448 340 521 330 -637 420 266 257 364 -110 430 -329 -455 53 126 679 -411 455 335 534 492 -256 337 -76 -328 327 66 502 309 519 26 641 -245 175 353 -482 499 681 -109 514 -454 -419 -146 -596 538 646 -479 -198 -233 409 53 584 -52 73 691 -625 241 -322 -361 472 -348 -463 301 -216 -468 35 284 -419 -258 -212 -611 394 -370 241 184 74 -654 -470 -462 -282 -141 541 130 -610 474 -461 431 556 -683 -478 23 683 -10 112 384 -695 512 345 -257 655 -623 537 -527 472 -448 40 -454 -45 507 -634 14 -444 359 490 126 -447 -183 641 -454 391 -183 -322 221 -274 550 -400 -675 248 -696 -10 287 567 151 -375 -583 -385 170 560 22 531 -411 194 485 -184 -569 576 -645 -643 -280 -628 -405 -160 -536 -463 154 375 -254 -298 459 -281 23 112 302 -697 696 35 -527 435 108 -221 454 -493 438 -541 282 591 451 -594 -376 -556 184 22 622 -307 -349 684 394 100 -591 520 553 -37 215 610 -690 -144 -254 -211 374 381 365 -218 -66 -121 265 5 316 -334 235 -14 144 651 279 -311 583 482 488 -140 635 242 457 -210 -350 288 667 534 -50 -265 510 82 -254 -337 432 -518 -69 -339 418 -347 -349 -65 -543 274 655 -598 -363 -166 156 438 -427 357 -241 677 -223 -646 -467 -37 -392 281 633 668 385 -308 -257 -272 426 -53 213 195 -24 660 242 -509 139 83 -247 -169 -193 -535 -140 -232 191 526 188 -554 -180 -534 493 -209 -668 415 -496 -111 -84 -426 282 -201 243 -423 40 564 -153 362 -498 566 676 509 -329 133 -32 -643 -18 -414 205 -502 -118 -592 -389 405 235 -353 -684 463 -341 -198 -243 449 -580 -387 101 487 127 -138 166 95 -13 -308 -242 -284 336 354 -498 -289 602 -132 -443 -299 280 -485 -525 -11 -265 -235 -189 -509 -569 678 -371 -359 -209 136 -388 -63 532 -530 -365 524 123 -472 206 -197 369 -689 309 39 -376 125 -271 -289 -680 487 -425 -625 366 39 34 -696 -422 339 -105 307 369 -93 111 126 645 165 435 427 246 560 167 -490 -348 482 -330 -27 -249 -119 395 696 -225 -219 637 335 -82 -560 -626 17 633 7 451 -111 -62 341 238 -201 -429 -81 694 -400 -536 -435 600 360 -554 -163 619 153 597 -426 610 -398 -75 -261 -162 -542 660 602 369 -17 468 641 132 -148 127 595 -50 -662 -274 -624 542 -249 -322 -517 -600 247 80 46 -275 273 413 40 -344 616 684 -247 -506 -555 -1 -676 -415 -87 382 -32 336 -155 -296 402 486 -132 137 244 -401 587 62 583 536 642 -174 -522 88 404 -652 335 607 -219 -249 469 -622 592 204 -397 -306 -461 455 697 -362 126 -434 -36 488 -574 -94 -595 -168 234 -485 -658 488 173 588 161 -279 214 578 -359 -338 116 -161 -666 -262 572 -417 79 -627 314 -246 -281 268 -506 391 -695 352 490 183 427 -460 609 -341 519 -103 11 126 103 -353 -625 -413 534 -448 653 -644 226 520 -316 -177 -232 -47 -59 -40 146 -16 -290 -547 -498 -169 -22 254 -689 -360 -333 446 586 537 559 687 -61 341 -505 -480 50 -172 -413 -608 -479 180 442 -666 -362 -70 -142 -689 -676 -20 19 -258 282 -379 442 -514 520 66 320 -29 23 104 256 115 -612 -651 -367 -354 -566 414 610 295 0 464 461 348 -564 680 541 -666 70 -294 -578 -502 299 210 -154 -674 -250 35 -477 79 -432 419 -668 -447 -598 514 -466 107 -102 93 386 -424 398 678 -374 -423 -322 189 -261 -107 136 296 -591 230 -413 -334 -490 -498 195 132 -601 -395 -451 -651 -389 56 -123 629 295 153 240 189 510 -637 219 156 174 473 102 682 334 659 195 176 119 -410 298 -604 -303 -347 -154 176 576 -125 -150 165 136 501 -46 -210 -184 -400 -17 -94 -72 51 41 -214 -33 405 154 165 511 429 72 -627 159 373 330 608 371 326 306 487 -565 423 532 -470 -145 -72 82 336 -94 90 -326 255 184 -599 -568 489 509 -301 -5 113 -163 128 294 624 -36 461 390 -214 -86 -134 8 334 517 -88 -223 167 371 638 396 -294 -514 452 609 -621 670 -580 -31 -192 -635 265 -57 -415 -576 120 -190 -78 404 475 58 -117 -457 -308 -89 -580 352 313 -574 396 -681 -493 403 -228 561 345 -458 492 272 -106 685 50 222 -268 -383 623 250 266 182 -379 640 220 -210 283 -104 -670 251 -30 167 -336 256 -480 -354 505 -360 -286 -275 -308 506 464 -338 -247 -602 -57 -51 -698 -226 -495 691 476 -590 -43 445 -54 414 500 -357 -175 -662 176 -429 -80 358 577 -377 -460 -168 -467 113 303 -532 179 -125 80 -170 -18 -673 -102 295 -546 -315 549 420 -162 36 32 530 223 -547 258 -55 149 -72 -4 382 -121 -140 310 -268 464 452 -265 -350 -268 -493 33 192 98 -506 639 161 -494 237 27 368 -47 345 456 202 -521 312 -480 -125 60 195 250 543 -474 435 -20 -432 -217 381 649 11 97 604 336 677 -667 228 -220 -554 506 275 -136 -213 -576 -418 318 -459 -423 485 -476 124 -148 -57 490 -560 -568 -154 -117 670 -457 699 174 695 -421 -215 -166 345 47 178 -61 61 342 -542 -138 -413 -543 408 -652 -413 -268 -500 498 -559 -631 76 -469 561 257 681 131 -17 452 -612 572 15 424 -579 -290 318 -662 -553 328 221 609 245 672 208 3 373 176 248 146 -678 -568 591 -149 -625 557 -574 -160 494 549 236 654 33 136 -608 366 440 119 -116 478 201 680 -125 -502 -683 -106 610 -118 477 -42 28 -451 -333 321 -328 511 128 194 23 109 261 -557 414 -448 -472 -563 534 35 -431 -350 -660 560 -321 -122 109 452 539 -681 -401 -206 479 -181 -583 -327 67 -253 -325 -243 -158 534 -32 397 -233 -689 -656 -97 -340 505 -471 -691 -468 13 -263 8 459 -348 -553 575 -282 -661 -535 -387 -639 552 -215 -309 561 -167 -378 36 -34 98 113 225 445 -572 185 589 -41 -314 415 -9 -651 -520 430 13 107 -688 680 -516 -264 -476 129 28 505 -287 -488 -77 679 420 424 489 517 214 470 344 213 -176 -337 683 71 487 576 334 56 -612 453 -197 294 58 -147 699 213 -470 -163 -395 -520 -337 -131 -399 464 -371 36 -561 -507 669 -92 110 427 359 560 -260 515 119 173 120 -439 404 -410 -565 290 -303 649 70 -130 49 -175 -293 -111 522 128 181 -629 -328 -19 213 42 -253 450]
14 Dec, 2011, Rarva.Riendf wrote in the 2nd comment:
Votes: 0
reply I dont understand your example
45	-34	8	7	48	-30
45 -34 8 7 48 <- max 55
45 -34 8 7 <- here I find the 63
45 -34 8 <- max 45
45 -34 <-max 74
45 <- max 74
45 11 19 26 74 44

For me 74 is the largest sum, or did I miss something in the problem definition?
14 Dec, 2011, Runter wrote in the 3rd comment:
Votes: 0
considering this set: [10, -10, 9, 2] the largest summed continuous range is [3..4]. or 9 + 2 = 11. No other continuous range has a higher sum. With a small set of data this is easy to eyeball. With a set like the one he gave us, this would be quite a lot of computation.
14 Dec, 2011, Rarva.Riendf wrote in the 4th comment:
Votes: 0
Quote
So for example, in the vector x

[45 -34 8 7 48 -30]

He states 63 as the max (8 7 48), I find 74 (45 -34 8 7 48), so I do not get it.

My algorithm is sucky as it needs to find the max number as many times as there are elements in the vector, and off course as many sums (but this one is pretty free if you do it binary, it is a simple &)
14 Dec, 2011, Tyche wrote in the 5th comment:
Votes: 0
[45 -34 8 7 48 -30] => 74 [0..4]

[10, -10, 9, 2] => 11 [0..3]

No?
14 Dec, 2011, Runter wrote in the 6th comment:
Votes: 0
Yes, my contrived example is flawed. :p
14 Dec, 2011, Tyche wrote in the 7th comment:
Votes: 0
Actually those are two good test data sets, since the results are known, and the second being a corner case.
15 Dec, 2011, Idealiad wrote in the 8th comment:
Votes: 0
Sorry, RR is correct. That's what I get for posting late. In the first example the largest one is [0…4]. If a mod wants to annotate that first post feel free.
15 Dec, 2011, Ssolvarain wrote in the 9th comment:
Votes: 0
By a show of hands, how many of you are actually robots posing as humans?
15 Dec, 2011, Idealiad wrote in the 10th comment:
Votes: 0
So I took my first shot at this; I haven't read more of the chapter yet.

A possible solution in Clojure, where the vector in the OP is v:

(apply 
max
(flatten
(for
[i (range (count v))]
[(apply + (take i v)) (apply + (drop i v))]))))


gives my first time, of 17214.598783 msecs, and an answer of 15966.
15 Dec, 2011, David Haley wrote in the 11th comment:
Votes: 0
This is a super-classic entry-algorithms course problem… typically solved most efficiently using dynamic programming, no?

You should rephrase the challenge as finding the most asymptotically efficient algorithm, to eliminate things like language speed.

You should also impose constraints on memory; if you allow the allocation of a very large block of memory the problem becomes substantially easier.
15 Dec, 2011, Idealiad wrote in the 12th comment:
Votes: 0
Explain that efficiency thing. I thought about language speed before the OP but I didn't really know how to deal with it, so I just punted.

'Easy' I'm not so worried about. How would you solve it DH?

edit: to add to the speed issue, I'm more interested in how people improve their speed relative to their previous attempts, than comparing speed among different folks' attempts, if that makes sense.
15 Dec, 2011, Tyche wrote in the 13th comment:
Votes: 0
Ssolvarain said:
By a show of hands, how many of you are actually robots posing as humans?

I used to be human, but then I took an arrow to a knee.
15 Dec, 2011, David Haley wrote in the 14th comment:
Votes: 0
See this as a starting point for what I meant about asymptotic efficiency.
http://en.wikipedia.org/wiki/Analysis_of...

Spoiler
The standard solution to this is iterating over the array, keeping track of the largest sum so far, and stopping when you hit a negative number.
This problem is so common it even has a Wikipedia page :-)
http://en.wikipedia.org/wiki/Maximum_sub...

The solution is basically one-dimensional dynamic programming.
15 Dec, 2011, Idealiad wrote in the 15th comment:
Votes: 0
OK I understand you now, you meant the O(n) stuff.
15 Dec, 2011, Runter wrote in the 16th comment:
Votes: 0
[336, 502, -557, -371, 507, -199, 665, -497, 452, 426, -56, -641, 641, -284, 603, -3, -445, -347, -531, -667, -403, -472, 43, -348, -229, -235, -370, 345, -563, 578, 109, 49, -520, 530, -612, -671, -69, -514, 138, 394, -367, 164, -89, -445, 221, -431, -571, -466, 358, 313, 564, -203, 13, 474, -603, -264, -681, -229, 481, 412, 488, 490, -38, 373, 666, 222, -101, -600, -259, -48, -86, -621, -169, -203, -166, 442, 43, 517, -681, 196, 347, 483, 37, -376, -469, 451, 229, 250, -675, -238, 563, 692, 486, -42, 281, -252, 251, -322, -122, -140, -251, -267, -42, 336, 240, 257, -301, -5, 423, 609, 690, -203, -114, 253, 541, 10, -329, 574, -250, -506, 621, -224, -317, -389, -236, 481, -364, 97, -561, 326, -95, -681, 400, 446, -118, -654, -285, 587, 18, -493, 18, 34, 374, 173, -394, 666, -161, 486, -656, -323, 49, 137, 178, -98, -627, -438, 485, -315, -97, 148, -343, -73, 411, 318, -687, 668, 154, 646, 576, -102, -297, 541, 571, 379, -71, -75, -5, 409, 328, -338, 660, -84, 407, 152, 197, 613, 607, -201, -88, -405, 131, 675, -546, -647, 176, 349, 567, 621, -262, 332, -403, -52, 623, 465, -464, -82, 525, 352, 591, -210, 62, 352, -351, -646, -554, 159, -467, -66, -248, 467, -60, 668, 396, 70, 672, -371, -561, -570, -212, 496, 673, -182, -19, 25, -231, -348, -156, 233, 642, -19, 171, 237, 23, -258, 379, -600, 110, 665, 266, -87, -265, 143, 619, 267, 653, 646, -21, 604, 449, 173, 363, 482, 184, -613, 487, 245, 52, -248, -638, 569, 126, 364, 689, -291, 250, -333, 485, -32, 337, 468, -305, -242, -545, -658, 338, -612, 341, 436, -337, 340, 477, -42, 75, 262, -208, -81, 28, 369, -464, -386, -474, 375, 34, -237, 154, -4, 19, -194, -48, -24, 483, 359, 474, -330, 691, -553, 187, -659, -522, 385, 59, 601, -90, 151, 61, 615, 416, -184, 164, -385, -434, 651, 551, 74, -520, -454, -191, -440, 479, -396, 31, -47, 429, 515, -392, 574, -571, -585, -580, -601, 226, 353, 462, 437, -182, 461, 444, -105, 686, -255, -671, -105, -168, 88, -425, -30, 681, -491, 290, -87, -306, -530, 27, 262, 539, 699, 652, 425, -166, 415, -527, -670, 504, 7, -609, 624, 148, 416, -601, 185, -252, 358, 121, -65, -256, 603, -268, 40, 505, -80, 448, -654, -448, 117, 207, 311, -102, 453, 568, 156, -113, 215, -275, -629, 70, -418, -694, -357, 524, -540, -408, 492, 348, 89, -631, 322, 120, 155, -16, 235, -19, 109, 319, -272, 470, 207, 465, 222, 683, -699, -120, -355, -156, -157, 458, -676, 47, -62, 492, 249, 41, -532, 90, 438, -555, -170, 8, -650, -663, 653, 612, -576, 531, 14, 460, 686, -504, -75, -269, -597, -367, 435, -505, 29, -390, 612, -543, -232, -318, -613, -604, 429, 368, 168, 68, -118, -49, -547, 699, -35, 610, -456, -359, 347, 284, 80, 77, -456, -392, -220, 605, 16, -608, 427, -481, -297, -409, -249, 77, 245, 71, -142, 205, 34, -360, -194, 104, -497, -249, 585, 535, 376, 560, -167, 361, -458, 598, -239, 375, 50, 238, -459, -322, 132, -475, -614, 414, -385, 555, 431, 634, 586, -446, 311, 389, 215, 103, 422, 548, 110, -460, -667, 280, -379, -31, -31, -172, 137, -118, -259, 200, 645, 249, 125, 183, -263, 697, 299, 27, 627, -359, -510, 62, -239, -179, -275, -518, 123, -65, 630, 87, 162, 524, 291, -675, -654, 109, -133, 445, -629, -261, -652, -92, -121, 588, 364, -609, -397, -16, -447, 343, -559, -495, 125, 29, 309, -353, -372, -168, -614, -238, -56, 488, 521, 665, 364, 189, -412, 490, -591, -676, -492, -162, -62, 24, 258, -515, -132, -127, 682, -624, 382, 36, -519, 521, 100, -270, 9, 45, 228, -375, -244, 688, 399, -149, -616, -635, 602, -462, -465, -32, -357, -453, -697, -24, 365, 658, -633, 339, -592, 118, -227, -321, -86, -175, -438, 130, -539, 538, -362, -369, 345, -685, 362, -1, -409, 244, 334, 264, -427, -555, 617, -99, 213, 1, -618, 261, -568, 383, -220, -560, -409, -460, -97, -52, 394, 573, -44, -394, -325, 442, 197, -126, 205, 396, -411, 32, -292, 371, -218, -2, 559, -292, -566, -208, -166, -29, -337, 647, -502, -69, 381, 320, 151, 80, -11, -260, -390, -332, 454, 113, 113, 3, -545, 550, 565, -509, -225, -145, -501, -494, -260, -71, 421, 115, 97, -679, 346, -178, 134, -162, -320, -111, 169, 48, -381, 296, -637, 32, 404, -490, 171, 562, -433, 196, -637, 253, -150, -72, 224, 570, 534, 98, -105, 309, -428, 223, -682, 376, -504, 270, 690, -340, 698, 272, -19, -608, -457, -468, -292, 443, -113, -370, 185, -433, 482, 697, -200, 677, 57, -231, 209, 142, -533, -130, -640, -17, -88, -422, -77, 60, -207, -148, -478, 214, 225, 239, 551, 342, -129, -642, -34, 207, -132, -224, -666, -590, 421, -431, 354, 335, -444, 571, -265, -349, 79, 47, -696, -605, -299, 673, -216, -132, -436, -231, -164, 365, -505, -161, -662, 524, 434, -699, -364, 420, -114, 383, -462, 409, -174, -221, 311, 261, 34, 368, -252, 283, 490, 464, -42, -544, -44, 237, -408, -481, -283, 654, 3, 668, -52, 501, 525, -299, 392, -199, -22, -209, 347, 400, -94, 429, -326, 528, -366, 357, 507, 533, -5, -682, -115, 200, 286, -105, 90, 322, -338, -331, -647, 421, -33, -137, 86, 480, 384, 36, -9, 331, -380, -79, 550, -302, 557, 97, 214, -607, -2, -639, 398, -660, -229, 282, -136, -325, 165, -511, -383, -433, 260, -188, -231, 46, -277, -277, 532, -26, -56, -472, -466, -259, 42, 360, 71, -430, -14, 413, -231, 446, 180, 384, 195, -273, 597, 558, 561, -508, 650, -285, 245, -314, -494, -287, -640, 5, 236, -24, 217, 321, -521, -458, 121, -468, -642, -351, 181, -593, -294, 282, 618, 619, 40, 76, 437, -72, 647, 676, 420, 261, 236, -693, 672, -498, -226, -438, 276, -578, 488, -497, -563, -145, -623, -310, -303, 509, 37, 271, -74, 610, -87, 558, 264, -27, 595, -556, 506, -381, -680, 135, -67, 189, 42, 691, 331, -53, -502, -573, 138, 302, 81, -645, -188, -627, -66, -251, -612, -253, 208, -403, 565, -160, -44, 388, -400, 650, 32, 64, 228, -294, 553, 18, 672, 435, -509, -276, 655, -628, 225, -594, -515, -11, -236, -587, -2, 188, -312, 260, 513, -428, -454, 244, 80, -27, 169, -564, 598, 390, 202, -391, -72, 320, -579, 40, -218, 529, 194, -330, -442, -2, 553, 218, -484, -589, -340, -70, -602, -689, -575, -620, -234, 374, 390, -446, 462, -545, -23, -567, -366, 623, 526, -422, 638, 136, 324, -487, 2, 632, -169, -365, 251, 331, 195, 228, -210, 11, 242, 407, 371, 281, -121, 362, -262, 687, 144, 569, 161, -49, 314, 516, -48, 438, -283, -185, -66, -528, -202, 674, -628, 684, -17, 474, 499, 291, -508, 213, 440, 195, -452, -126, -575, 247, 563, -616, 142, 263, -553, -326, 33, -322, 298, -310, -317, 692, -213, 696, -521, 438, -275, -180, -104, -252, 129, 476, -257, -529, 97, 521, 598, 548, 238, -418, -656, -653, 458, -255, 73, 351, -561, 128, 40, 137, 74, -180, 276, -352, -611, -309, 698, -315, -445, 107, 343, 476, -502, 462, -248, 7, -604, -4, -387, 608, 622, -86, -536, 191, 405, 639, -402, 193, 216, -233, 140, 7, -81, -536, 449, 543, 125, 159, 217, 558, -655, -116, -354, 414, 232, -643, -242, 53, 615, -64, 681, 598, 377, -287, -105, 230, 440, -570, -426, -377, 165, -591, -492, -633, 598, 409, -186, -194, 151, 513, 517, 667, 386, -382, -643, 394, -517, -495, -658, -1, 49, -298, -225, -568, -422, -181, -128, 459, -235, -332, -685, -580, -452, -693, 245, -649, 533, 102, -652, -89, 133, 613, 157, 484, -249, 35, -609, 454, -648, -11, -654, -547, -357, 452, 32, -244, -525, 279, 330, 138, -693, 139, -359, -116, -17, -117, -541, 669, 432, -336, 129, 607, -557, -625, -610, -45, -89, 511, 139, 196, -310, -241, 429, 86, 522, -260, 76, 273, -191, -190, -306, 39, -648, 685, -268, -583, 389, 475, 510, -335, -562, 696, -511, 175, -351, 86, 160, -124, -577, -497, -508, 26, -477, -344, -15, -166, -52, -694, 194, 672, 266, 564, 406, 201, 557, -186, -266, 111, -284, -358, 264, -262, 421, 179, 499, -13, 578, 549, -401, 681, 606, 678, -373, -308, 108, 232, -181, 433, -577, -312, 279, 675, -332, 146, -539, 468, -601, -533, 138, -205, 5, -86, -398, 488, -324, 540, 3, -478, 435, 532, 132, -11, -292, -84, -172, -504, 546, 418, -523, -577, -451, -4, 478, -676, 301, 514, 369, 343, -179, -133, -498, 698, 235, -153, -86, 317, -207, -539, -334, -216, -252, 265, 454, 185, 469, 138, 220, -424, 115, 464, 364, -180, 540, -37, 692, 681, 615, 334, -210, -231, -207, -60, 185, 291, 137, -373, 75, 268, 520, 690, -203, -203, 282, -134, 67, -603, -84, -299, 205, 76, -614, -224, -351, 660, 229, 605, 67, 152, -344, -102, -522, -587, -515, -398, 662, 606, 345, 431, 85, -524, -329, -302, 118, 99, -208, 533, -369, -638, -598, 16, -87, 206, -516, 398, 551, -222, 409, -274, -695, 655, 179, 592, -13, 364, 43, -92, -610, -428, -371, 423, 404, 73, -304, 134, -479, -186, 29, -303, 49, -183, 579, 667, -292, 51, 66, -269, 649, 3, -183, 30, 110, -104, 530, -604, -29, 356, -535, -293, -325, -457, 191, 11, 688, -61, -124, 136, 378, 525, -267, -88, -187, 197, 99, -510, 511, -683, -74, 360, -142, -418, -555, 323, -585, 314, 326, -310, 556, 251, 443, -3, 517, 348, -450, -363, 152, -135, -71, 697, -592, -95, 56, 75, -249, -455, -235, 131, -598, -655, -16, -173, 642, 308, 432, 218, 228, 541, 7, -399, -417, 571, -16, -128, -406, 665, 554, -503, 573, -392, 527, -392, 285, -141, 142, 544, 385, 91, 461, -187, -64, 51, 330, -142, -463, 288, -320, 39, -180, 133, 325, 529, 262, 424, 103, -515, 20, 624, 270, 658, -184, -524, -69, -33, 0, -525, 282, 314, 225, 249, -247, -557, -375, 331, -510, -73, 430, 490, 419, 518, -611, -476, -440, -567, -676, 151, -246, -508, -387, 39, 620, -5, 170, 367, 570, 407, -457, 269, -137, -91, -478, 426, -658, 186, 248, -677, 5, -398, 565, 415, -121, 540, 217, 641, -213, -442, 265, 467, -278, 191, -238, -572, -580, 16, -667, 447, -391, -32, -653, -204, -171, 213, -326, 420, -346, -433, -51, 642, 518, 618, 290, 174, -308, -489, 618, 29, -410, 690, -61, 216, 522, 235, 401, 678, -77, 106, 258, 424, -183, -598, -154, -15, -446, 497, -421, -179, -650, 17, 597, 694, -599, 549, -23, -340, -47, -698, 252, 322, -92, 198, 214, -411, -584, -345, 498, 352, -184, -281, 369, -346, -278, 518, -696, -190, -124, -89, 286, -346, -195, -466, -541, 666, 43, 173, -674, -395, -287, -595, 177, -425, 316, -254, 189, 585, -253, -507, 542, -277, 519, -283, -567, 488, 192, -369, 81, 465, 456, 106, 606, 5, -683, 360, 77, -302, 89, -180, 342, -670, -558, -647, 61, -516, -130, 194, -368, 37, 397, -134, -434, -267, -139, 139, -158, -502, -218, -646, -71, 371, -86, -688, 630, 29, 96, 84, 438, -502, 114, -419, -110, -102, -565, 111, -485, -493, -271, 46, 140, -476, -357, -16, 159, 520, -542, -6, -479, -667, 223, 205, 288, -484, 144, 141, 464, -128, 587, 268, -587, 370, -633, 441, 48, -271, 388, -378, 338, 519, -562, -380, -202, -274, 251, 63, -686, -61, 256, 17, -202, -331, -547, 309, 510, 166, 243, 385, 570, 95, -282, 238, -220, -563, 691, 50, -102, 355, -674, 621, -511, -170, -106, 55, -656, -605, 462, -553, 659, 88, -646, -131, -426, -560, -98, 276, -169, 218, -79, 502, 562, -352, -476, -663, -657, -335, -165, 546, -296, -471, 42, -440, -599, -381, -288, 261, 504, 401, 443, 580, 101, 322, -500, 678, 673, 486, -49, -127, 644, -623, 323, 80, 105, 396, 225, -599, -144, 184, -660, -376, 228, -125, 170, 414, 492, -495, -68, 173, 646, -389, 306, -2, -606, -252, -435, -106, -489, 651, 537, -434, -563, -394, -21, 464, -508, -49, -50, 139, 348, -301, 101, 575, -665, -160, 400, -542, -577, -207, 377, -292, -575, 146, 327, 683, 635, 381, -289, -428, 339, 56, -155, 60, -195, 221, 292, -399, -24, -5, -28, 258, 253, -415, -638, -420, -243, -497, -30, -92, 533, -115, 119, 194, -678, 42, 438, -45, -618, -677, 19, 68, -402, 209, -357, 216, 252, -219, 322, 81, 346, -271, 694, 560, 556, -341, 435, 71, 560, -689, -613, 250, 226, 160, -562, 479, 328, 387, 421, -12, 348, -413, 596, 10, 72, -68, -44, 98, 681, -471, 362, -299, -503, -21, -433, 527, 367, -525, -171, 422, -77, -463, 554, -463, 610, 181, -639, 514, -185, 578, 115, 559, 575, 120, -8, -144, -249, 92, -673, -241, 164, 180, 525, -186, -559, -240, -579, 63, 205, 495, 437, -144, 612, 271, -205, -389, -419, 456, 643, 383, -291, -349, 300, -256, -409, 33, 448, -511, 43, -685, -143, 264, -514, 312, 282, -562, -408, 68, 14, 41, 92, -102, -533, 435, -538, -432, -664, -443, 568, 151, -324, 32, -264, 312, -106, 317, 310, 633, 118, -451, -464, 644, 698, -113, -571, -644, -63, 286, 670, -153, -261, -54, 453, -71, -60, -666, -578, 282, -471, 242, 148, 667, 487, -516, 203, -408, 0, 248, -192, 401, 423, -553, 425, 506, -24, 616, 600, 314, 46, 297, -91, 392, -82, 355, -213, -448, -526, -327, 506, -120, 6, 557, -122, -587, 386, -347, 174, 454, 589, 490, -315, 558, 569, 396, 433, 294, 543, -520, 389, 461, 362, -666, -637, -482, -578, -311, -491, 445, -633, 276, 40, 357, 282, 353, 24, -421, 25, 242, 418, -689, -16, 169, 81, 19, -557, 500, -690, 66, -510, 545, 141, -578, -586, -440, 693, -465, -482, 344, -599, 388, 682, -483, -440, 658, 347, 141, 256, 356, -353, -164, -138, -218, -453, -442, 336, -133, 684, -73, 590, 460, 514, -430, 678, 457, 639, -290, 158, 574, -557, -382, -340, 161, 665, 578, -506, -494, 277, 421, 180, -100, 658, -577, -502, 364, 605, -144, 64, 333, 336, 356, -313, 440, -169, 177, -132, -35, 279, 256, 643, -381, 295, -404, -200, -460, 463, -399, 273, 386, 677, 135, 422, 131, 168, -188, -640, 313, -97, 535, -81, -85, -290, 270, 324, -645, 417, 599, 445, -642, 2, -298, 69, 47, 209, -288, 153, -532, -43, -538, -509, 353, 72, 6, -265, -143, 349, -692, 636, 457, -382, -246, -437, 131, 103, -465, -168, 436, 218, -368, 563, -646, -539, 137, -560, 161, 635, -355, 549, 124, 356, 88, -112, -458, 10, -291, 645, -291, -195, 325, 330, -149, 29, 26, -609, -238, 417, 363, 70, 540, -255, -63, 138, 204, 250, -507, 244, 195, -527, -519, -217, -35, 33, -689, 508, -655, -353, 625, 150, 343, -631, -6, 212, -340, -524, -492, -403, -444, 352, 108, 430, -100, 321, 611, 418, -404, 224, 200, 447, -447, -454, 133, -159, 556, 480, -77, -244, -638, -180, 568, 116, -220, -509, 385, -220, -635, -168, 569, -142, -205, 502, 415, 618, 21, 228, -343, -251, -315, 274, -112, -294, 488, -694, 637, -248, 619, 480, -329, -89, -383, -79, -154, -624, -549, 302, -292, -637, -534, -568, 145, 171, 345, -333, -310, -574, -15, -690, 431, 476, -331, 533, -291, -400, -408, -36, 500, -126, -448, -583, 9, 429, 2, 246, 434, -697, 406, -204, -81, 185, -680, 541, -612, 353, -96, -482, 483, 304, -551, -34, 543, -623, -622, 255, 484, 271, 666, 174, -674, -97, 0, -509, 319, 63, 282, 682, -528, 596, -666, 325, -77, 429, 608, -508, 516, -260, 451, 149, -333, 77, 599, -684, -86, 509, -278, -107, -683, 600, -534, 304, 236, 628, 215, 40, 41, 602, 438, -689, -266, -619, -345, 189, -426, -364, -690, 589, -302, 76, -510, -99, -612, 620, 280, -269, -152, 437, 657, -268, 273, 664, 46, -119, 435, 445, -60, 621, -287, 364, -56, 466, 39, 595, 653, 331, -239, -121, -582, 102, -61, -92, 122, -56, -478, -516, 10, 210, -568, -687, 330, -626, 677, -618, 543, -11, -342, 226, -583, -655, -144, 174, -345, -610, -647, 83, -635, -392, 237, -458, -472, -560, -79, -202, -441, -300, -136, 604, -346, -325, -441, 319, -530, 276, -305, -298, 319, -564, -194, 4, -551, 599, -23, 57, -475, -208, 341, -667, -525, 18, 506, -159, 224, 266, 682, 99, 261, 464, 688, -669, -438, 421, 104, -170, 98, -514, 699, -111, 73, 650, 542, 60, 503, -362, 104, -135, -234, 536, 272, 558, -183, 455, -333, -431, 631, -113, -681, 175, -75, -434, -479, -347, -671, -494, 264, 243, -232, 136, 83, 538, -650, 429, -697, 421, -492, 202, 183, -127, -567, -356, 141, -382, 353, 547, -162, 202, -452, -277, 26, 317, -512, 539, 545, -15, 414, -221, -451, -614, 128, 534, -205, 227, -89, -145, -678, 355, -638, 223, 222, 245, 628, -314, -142, -584, 399, -435, -34, 513, -471, 417, 342, 101, 92, 356, 256, 291, 666, -563, -260, -223, -334, 294, 589, 389, 475, 321, -360, 672, 269, -570, -190, 689, -423, 334, -110, 224, 262, -349, -141, -521, -533, -570, 587, 392, 665, -299, -669, -132, 403, 458, 602, -572, -492, -292, 477, -99, 80, 558, 17, 416, -572, 228, -615, 445, 661, 517, 68, 670, 299, 109, 664, 493, 96, -650, 390, 39, -263, 422, 171, 528, -626, -518, -50, 321, -588, 390, 81, 691, -210, 431, -171, 567, 238, -20, 328, -282, 496, 636, 74, 200, -435, 19, 229, 603, 181, 642, 604, -274, -649, -614, -624, -501, -7, 429, 285, -388, -96, -335, 424, 352, 157, -385, -42, -31, 207, 699, 513, -148, -179, -336, 68, -494, 5, -367, 648, -427, -410, 102, -351, 7, -155, 95, 217, -100, -335, 543, 341, 642, -627, -653, -393, -623, -540, -534, 190, -46, -20, 350, -348, -69, -200, 28, -419, 536, 406, 219, 467, -545, -261, 451, -365, -223, 539, -412, -309, -601, 65, 679, 657, -102, 174, -49, -82, -295, 357, 156, 262, 169, 461, 183, 361, 345, 439, -388, 370, -305, 42, -418, 413, -632, 313, 272, -46, -679, -524, -39, 377, -501, 463, 318, -120, 634, -662, 504, 639, 504, 327, -692, -245, -583, -606, -534, -166, -343, -10, -451, 688, -276, -469, -278, 444, 359, 689, 411, 101, 103, -551, 172, 665, 615, -553, -200, -113, 148, -91, 466, -614, -29, -641, 338, -304, 183, 471, 358, -419, -101, -610, -610, 9, -218, 643, -585, -290, 288, -207, -669, -293, -587, -522, 24, -626, -74, -466, -422, 160, 493, -86, -655, -8, 389, 105, -550, -637, -282, 155, -227, 560, 518, -64, 15, 285, -86, -270, -290, -5, -669, -426, 1, 689, -87, 346, -526, 173, -23, 583, 632, -578, -655, -143, -55, 113, -440, 193, -632, -616, 604, -392, 430, -62, 57, 574, 265, -330, 221, -346, -208, -511, -239, 592, -213, -105, 319, 491, -322, -225, 315, 686, 230, -217, 456, 274, 311, -567, -72, 685, 39, -38, 181, -293, -463, -376, 537, 162, -8, 569, 148, -212, 415, -646, 615, -285, -557, 153, -654, 426, 163, -452, -409, -503, -662, -513, -46, 155, -328, -595, -404, -222, -673, -369, 349, 697, 633, 580, 332, 222, 36, 85, -170, 194, -444, -510, -193, 667, -32, 191, 420, -569, -309, -527, -269, -254, 17, -430, 105, -377, -666, -261, -485, -348, 77, -391, 47, 514, 152, 24, 167, -463, 684, 662, -166, 53, -182, 613, -646, 128, 376, -664, -491, -36, 23, 664, -556, -500, 225, -511, 638, -185, -238, -308, -286, -461, 34, -252, -214, -76, -133, -277, 517, -158, 627, 336, -490, -234, 67, -323, 119, 431, -667, 156, -692, 685, 567, -75, 32, -586, 253, -622, 469, -130, -6, -611, -199, 454, 463, -610, -483, -280, -287, -77, 402, -89, -575, 241, 63, 307, -584, 508, 428, 264, -315, 136, 690, 665, -501, 308, -648, 594, -502, 500, 243, 518, 380, 22, 537, 568, -320, -379, 80, -338, -521, 72, -382, 298, -669, 253, -76, 221, -365, 589, -252, 681, 665, 603, 194, -562, 79, -200, -50, -485, -206, 299, -519, 548, -10, 416, 323, -533, 585, 78, -120, -421, -435, 574, 659, -626, -682, -242, -681, -143, -581, -483, 237, -53, -290, 633, 551, -444, 46, 623, -170, -646, -425, 439, 568, -271, -190, -238, -297, -122, -272, -280, 307, -108, 219, -699, -570, 569, -213, 614, -493, -312, -243, -451, 387, 213, -88, -327, 42, -413, 434, -126, -422, -339, -44, -51, 671, -425, -147, -652, 303, 392, 114, -53, 524, -333, 147, -319, -184, 518, 282, 61, -282, 184, 598, -243, -264, -4, -679, 660, -381, -446, -60, 388, 6, -349, 170, -323, 213, -192, -44, -484, 195, 31, 668, -310, -337, 431, 77, -606, 501, -210, 31, 305, 374, -374, -424, -350, 584, 24, 504, 523, 610, 247, -223, 462, 195, -26, 130, -151, -685, -537, -476, -272, 24, 109, -406, 159, -590, -84, 348, 381, -147, 672, 420, -350, -145, 410, -429, -445, -614, 375, 219, 74, 95, -490, 0, -122, -342, 636, 463, 180, 274, 559, 562, 13, -246, -423, 118, -245, -97, 570, -574, -157, 471, 571, -221, 522, -322, 675, 646, -633, 467, 508, 93, -580, -126, 566, 642, -411, 169, -308, 324, 556, 366, 137, 249, 407, 510, -40, -302, 496, -47, 407, 545, 592, -143, -257, -418, -222, 373, 155, -632, -598, -603, 472, -206, -72, -613, 534, -175, -685, 667, 176, -476, -70, 140, -479, 503, 608, 557, 651, -669, -678, 694, 103, 419, -230, -251, -214, 201, -569, 110, -490, -363, 147, -622, -59, 644, -183, -279, -262, 590, -564, 92, -34, -687, 206, 264, 464, 9, 165, -421, 112, -330, 232, 156, -602, 223, -250, 295, 204, -667, 48, -584, 211, 432, -463, 162, -51, -298, 401, -362, 681, 349, -475, -466, -274, -629, -88, 295, 692, 268, -277, 620, -694, -102, 228, 214, -329, 47, 117, -488, -514, -113, -658, -81, 200, 145, -443, -498, -670, 558, -13, 611, 123, 171, 101, -66, -339, -74, 526, -273, -531, -191, -131, 257, 528, -600, -406, -208, 639, -245, -219, 549, -404, 533, -57, -618, 23, -521, -54, -534, 19, 613, 53, 178, -476, 440, 329, -628, 670, 490, -362, -218, -65, -499, 256, 16, 453, 335, 431, 31, -63, 225, -326, 604, -54, 120, 510, 445, 590, 281, -173, 506, -234, 444, 348, 623, -27, -692, 293, 540, 448, 340, 521, 330, -637, 420, 266, 257, 364, -110, 430, -329, -455, 53, 126, 679, -411, 455, 335, 534, 492, -256, 337, -76, -328, 327, 66, 502, 309, 519, 26, 641, -245, 175, 353, -482, 499, 681, -109, 514, -454, -419, -146, -596, 538, 646, -479, -198, -233, 409, 53, 584, -52, 73, 691, -625, 241, -322, -361, 472, -348, -463, 301, -216, -468, 35, 284, -419, -258, -212, -611, 394, -370, 241, 184, 74, -654, -470, -462, -282, -141, 541, 130, -610, 474, -461, 431, 556, -683, -478, 23, 683, -10, 112, 384, -695, 512, 345, -257, 655, -623, 537, -527, 472, -448, 40, -454, -45, 507, -634, 14, -444, 359, 490, 126, -447, -183, 641, -454, 391, -183, -322, 221, -274, 550, -400, -675, 248, -696, -10, 287, 567, 151, -375, -583, -385, 170, 560, 22, 531, -411, 194, 485, -184, -569, 576, -645, -643, -280, -628, -405, -160, -536, -463, 154, 375, -254, -298, 459, -281, 23, 112, 302, -697, 696, 35, -527, 435, 108, -221, 454, -493, 438, -541, 282, 591, 451, -594, -376, -556, 184, 22, 622, -307, -349, 684, 394, 100, -591, 520, 553, -37, 215, 610, -690, -144, -254, -211, 374, 381, 365, -218, -66, -121, 265, 5, 316, -334, 235, -14, 144, 651, 279, -311, 583, 482, 488, -140, 635, 242, 457, -210, -350, 288, 667, 534, -50, -265, 510, 82, -254, -337, 432, -518, -69, -339, 418, -347, -349, -65, -543, 274, 655, -598, -363, -166, 156, 438, -427, 357, -241, 677, -223, -646, -467, -37, -392, 281, 633, 668, 385, -308, -257, -272, 426, -53, 213, 195, -24, 660, 242, -509, 139, 83, -247, -169, -193, -535, -140, -232, 191, 526, 188, -554, -180, -534, 493, -209, -668, 415, -496, -111, -84, -426, 282, -201, 243, -423, 40, 564, -153, 362, -498, 566, 676, 509, -329, 133, -32, -643, -18, -414, 205, -502, -118, -592, -389, 405, 235, -353, -684, 463, -341, -198, -243, 449, -580, -387, 101, 487, 127, -138, 166, 95, -13, -308, -242, -284, 336, 354, -498, -289, 602, -132, -443, -299, 280, -485, -525, -11, -265, -235, -189, -509, -569, 678, -371, -359, -209, 136, -388, -63, 532, -530, -365, 524, 123, -472, 206, -197, 369, -689, 309, 39, -376, 125, -271, -289, -680, 487, -425, -625, 366, 39, 34, -696, -422, 339, -105, 307, 369, -93, 111, 126, 645, 165, 435, 427, 246, 560, 167, -490, -348, 482, -330, -27, -249, -119, 395, 696, -225, -219, 637, 335, -82, -560, -626, 17, 633, 7, 451, -111, -62, 341, 238, -201, -429, -81, 694, -400, -536, -435, 600, 360, -554, -163, 619, 153, 597, -426, 610, -398, -75, -261, -162, -542, 660, 602, 369, -17, 468, 641, 132, -148, 127, 595, -50, -662, -274, -624, 542, -249, -322, -517, -600, 247, 80, 46, -275, 273, 413, 40, -344, 616, 684, -247, -506, -555, -1, -676, -415, -87, 382, -32, 336, -155, -296, 402, 486, -132, 137, 244, -401, 587, 62, 583, 536, 642, -174, -522, 88, 404, -652, 335, 607, -219, -249, 469, -622, 592, 204, -397, -306, -461, 455, 697, -362, 126, -434, -36, 488, -574, -94, -595, -168, 234, -485, -658, 488, 173, 588, 161, -279, 214, 578, -359, -338, 116, -161, -666, -262, 572, -417, 79, -627, 314, -246, -281, 268, -506, 391, -695, 352, 490, 183, 427, -460, 609, -341, 519, -103, 11, 126, 103, -353, -625, -413, 534, -448, 653, -644, 226, 520, -316, -177, -232, -47, -59, -40, 146, -16, -290, -547, -498, -169, -22, 254, -689, -360, -333, 446, 586, 537, 559, 687, -61, 341, -505, -480, 50, -172, -413, -608, -479, 180, 442, -666, -362, -70, -142, -689, -676, -20, 19, -258, 282, -379, 442, -514, 520, 66, 320, -29, 23, 104, 256, 115, -612, -651, -367, -354, -566, 414, 610, 295, 0, 464, 461, 348, -564, 680, 541, -666, 70, -294, -578, -502, 299, 210, -154, -674, -250, 35, -477, 79, -432, 419, -668, -447, -598, 514, -466, 107, -102, 93, 386, -424, 398, 678, -374, -423, -322, 189, -261, -107, 136, 296, -591, 230, -413, -334, -490, -498, 195, 132, -601, -395, -451, -651, -389, 56, -123, 629, 295, 153, 240, 189, 510, -637, 219, 156, 174, 473, 102, 682, 334, 659, 195, 176, 119, -410, 298, -604, -303, -347, -154, 176, 576, -125, -150, 165, 136, 501, -46, -210, -184, -400, -17, -94, -72, 51, 41, -214, -33, 405, 154, 165, 511, 429, 72, -627, 159, 373, 330, 608, 371, 326, 306, 487, -565, 423, 532, -470, -145, -72, 82, 336, -94, 90, -326, 255, 184, -599, -568, 489, 509, -301, -5, 113, -163, 128, 294, 624, -36, 461, 390, -214, -86, -134, 8, 334, 517, -88, -223, 167, 371, 638, 396, -294, -514, 452, 609, -621, 670, -580, -31, -192, -635, 265, -57, -415, -576, 120, -190, -78, 404, 475, 58, -117, -457, -308, -89, -580, 352, 313, -574, 396, -681, -493, 403, -228, 561, 345, -458, 492, 272, -106, 685, 50, 222, -268, -383, 623, 250, 266, 182, -379, 640, 220, -210, 283, -104, -670, 251, -30, 167, -336, 256, -480, -354, 505, -360, -286, -275, -308, 506, 464, -338, -247, -602, -57, -51, -698, -226, -495, 691, 476, -590, -43, 445, -54, 414, 500, -357, -175, -662, 176, -429, -80, 358, 577, -377, -460, -168, -467, 113, 303, -532, 179, -125, 80, -170, -18, -673, -102, 295, -546, -315, 549, 420, -162, 36, 32, 530, 223, -547, 258, -55, 149, -72, -4, 382, -121, -140, 310, -268, 464, 452, -265, -350, -268, -493, 33, 192, 98, -506, 639, 161, -494, 237, 27, 368, -47, 345, 456, 202, -521, 312, -480, -125, 60, 195, 250, 543, -474, 435, -20, -432, -217, 381, 649, 11, 97, 604, 336, 677, -667, 228, -220, -554, 506, 275, -136, -213, -576, -418, 318, -459, -423, 485, -476, 124, -148, -57, 490, -560, -568, -154, -117, 670, -457, 699, 174, 695, -421, -215, -166, 345, 47, 178, -61, 61, 342, -542, -138, -413, -543, 408, -652, -413, -268, -500, 498, -559, -631, 76, -469, 561, 257, 681, 131, -17, 452, -612, 572, 15, 424, -579, -290, 318, -662, -553, 328, 221, 609, 245, 672, 208, 3, 373, 176, 248, 146, -678, -568, 591, -149, -625, 557, -574, -160, 494, 549, 236, 654, 33, 136, -608, 366, 440, 119, -116, 478, 201, 680, -125, -502, -683, -106, 610, -118, 477, -42, 28, -451, -333, 321, -328, 511, 128, 194, 23, 109, 261, -557, 414, -448, -472, -563, 534, 35, -431, -350, -660, 560, -321, -122, 109, 452, 539, -681, -401, -206, 479, -181, -583, -327, 67, -253, -325, -243, -158, 534, -32, 397, -233, -689, -656, -97, -340, 505, -471, -691, -468, 13, -263, 8, 459, -348, -553, 575, -282, -661, -535, -387, -639, 552, -215, -309, 561, -167, -378, 36, -34, 98, 113, 225, 445, -572, 185, 589, -41, -314, 415, -9, -651, -520, 430, 13, 107, -688, 680, -516, -264, -476, 129, 28, 505, -287, -488, -77, 679, 420, 424, 489, 517, 214, 470, 344, 213, -176, -337, 683, 71, 487, 576, 334, 56, -612, 453, -197, 294, 58, -147, 699, 213, -470, -163, -395, -520, -337, -131, -399, 464, -371, 36, -561, -507, 669, -92, 110, 427, 359, 560, -260, 515, 119, 173, 120, -439, 404, -410, -565, 290, -303, 649, 70, -130, 49, -175, -293, -111, 522, 128, 181, -629, -328, -19, 213, 42, -253, 450]

Might save a kindrid spirit a little time.
15 Dec, 2011, Rarva.Riendf wrote in the 17th comment:
Votes: 0
My algo in pseudo code btw: (I gave up coding it, as it requires know how in bit fiddling and I dont even remember the syntx to do that…)

struct max {
int value;
int position;
}
data[nbElements] = {x,y, z, ….};
index = nbElements
max tempMax;
max finalMax;

while (nbElements) {
nbElements–;
sum (data, (switch(data, sizeof(int)) <- (if data is 1 2 3 it does 1 2 3 + 0 1 2 next loop it will be 1 3 5 + 0 0 1) I know it is possible in binary with the appropriate << and &
tempMax = findmax(data) <- find the highest value and its position, and this can be heavily and easily parallized if needed
finalMax = maxof (temMax,finalMax) <- pick the highest one
}

I think that translate in O(n^2) that is not vey nice but easy (for the one that know how to code the bit bashing part) to code and read :P
15 Dec, 2011, Sharmair wrote in the 18th comment:
Votes: 0
Idealiad said:
So I took my first shot at this; I haven't read more of the chapter yet.

A possible solution in Clojure, where the vector in the OP is v:

(apply 
max
(flatten
(for
[i (range (count v))]
[(apply + (take i v)) (apply + (drop i v))]))))


gives my first time, of 17214.598783 msecs, and an answer of 15966.


I got a bit different answer: Start = 58, end = 569, sum = 21494 in 31uS
using MSVC++ 6.0 running on my old (2005) windows XP computer.
The way I did it was with a single scan through the data, keeping track of
the max sum as I went. The scan code was:
int rstart = 0;
int rend = 0;
int maxsum = 0;
int csum = 0;
int start = 0;
for(int current = 0; current < size; ++current){
csum += data[current];
if(csum < 1){
start = current+1;
csum = 0;
}else if(csum > maxsum){
rstart = start;
rend = current;
maxsum = csum;
}
}

It works on an array called data, with a number of elements of size.
15 Dec, 2011, Twisol wrote in the 19th comment:
Votes: 0
Well, first thing I notice is that you can treat contiguous sets of positive and negative numbers as single units. If a positive you've included in your solution is bordered by another positive that isn't, you can only add to the total by including it as well. Likewise, the total can only decrease in the same situation with negatives.

Incidentally, the first and last items in the solution will always be positive (unless there aren't any positives in the set to begin with). If you have a negative on the edge of your set, simply shrinking to un-include it would increase your total.

So… okay. I would start by going over the whole thing and partitioning it up into like-signed sets. And I'd keep a list mapping the ranges of these sets with their sums. Then I would repeatedly iterate over these islands, attempting to join positives separated by a smaller negative so that the "islands" consistently increase over time. When I hit the point where no island can be joined with a neighbor without losing value, we've found our maxima. From there, it's a matter of comparing them and finding out who has the largest magnitude.

<time passes>

Okay! Here's my work. It seems to work properly, though I don't see an easy way of checking the answer for the giant vector of numbers given.

$ time ruby vector.rb
[3728…3823, 14004]

real 0m0.285s
user 0m0.340s
sys 0m0.028s


# Isolate regions of positive and negative numbers
def partition (v)
sets = []

left = 0
i = 1
v.each_cons(2) do |l, r|
# are the signs different?
if (l >= 0) != (r >= 0)
sets.push [(left…i), v[left…i].reduce {|a, n| a + n}]
left = i
end
i += 1
end

sets.push [(left…i), v[left…i].reduce {|a, n| a + n}]
end

# Remove negative regions from the front and back - they'll never be included.
def trim! (sets)
sets.shift if sets.first[1] < 0
sets.pop if sets.last[1] < 0
end

# Merge adjacent regions of positive over a lesser region of negative.
def merge! (sets)
original_length = sets.length

(sets.length-3).step(0, -2) do |i|
left, neg, right = sets[i], sets[i+1], sets[i+2]

if [left[1], right[1]].min + neg[1] > 0
sets[i] = [(left[0].first…right[0].last), left[1] + neg[1] + right[1]]
sets.delete_at(i+2)
sets.delete_at(i+1)
end
end

sets.length != original_length
end

def calculate (v)
# Partition the vector into regions by sign.
sets = partition v

# If there's only one entry, return it, whether it's positive or negative.
return sets[0] if sets.length == 1
# Remove negatives from the front and back.
trim! sets
# If there's only one now, it's the only positive island, so return it.
return sets[0] if sets.length == 1

# Iteratively merge adjacent regions to create larger regions
nil while merge! sets

# We have our maxima. Return the largest of our remaining regions.
sets.reduce {|a, x| x[1] > a[1] ? x : a}
end


(EDIT: Well, based on other answers, it looks like this isn't complete yet. From some debug output, I think it needs to be able to merge groups that are separated by more than one negative region… time to work on that a bit.)
15 Dec, 2011, Omega wrote in the 20th comment:
Votes: 0
Tyche said:
Ssolvarain said:
By a show of hands, how many of you are actually robots posing as humans?

I used to be human, but then I took an arrow to a knee.


Skyrim arrow to the knee meme FTW!
0.0/78