Given n integers (some negative), find the largest sum of a contiguous, non-empty block — e.g. the best run of days in a list of daily profits and losses.
Write Kadane computing it twice: by brute force (every start, extending the running sum to every end, counting additions) and with Kadane's algorithm (one pass: the best sum ending at i either extends the best sum ending at i − 1, if that is positive, or starts fresh at i). Print the sum, the first block that achieves it, whether both methods agree, and both operation counts.
For the input
9
-2 1 -3 4 -1 2 1 -5 4
the program prints
Maximum subarray sum: 6
From index 3 to 6 (4 elements)
Brute force agrees: true
Additions: brute force 45, Kadane 9