Lost Treasure of Arrayland: A Story of Maximum Subsegment Sum

General
1

:glowing_star: Lost Treasure of Arrayland: A Story of Maximum Subsegment Sum

Learn Kadane’s Algorithm with C++, Java, and Python

:man_mage: The Tale Begins…

In the mystical land of Arrayland, a wandering adventurer comes across a long path of numbers — each number represents treasure (+ve) or traps (-ve) scattered across a magical trail. The adventurer wants to travel only once, choosing a continuous path that gives the maximum net treasure without turning back.

However, if all paths are filled with traps (negative numbers), he decides not to go at all — choosing 0 treasure instead.

Can you help our adventurer find this maximum treasure?

image
image785×778 209 KB

:bullseye: Problem Statement

Given a sequence of n integers (which may be negative), find the maximum sum of any consecutive sub-segment.
If all sub-segment sums are negative, return 0.

:inbox_tray: Input Format

  • A single line with n followed by n integers.
  • 1 ≤ n < 1000
  • Each number: |ai| < 10000

:outbox_tray: Output Format

  • A single integer: maximum subsegment sum (or 0 if all sums are negative).

:test_tube: Sample Input

6 -2 11 -4 13 -5 -2

:white_check_mark: Sample Output

20

:abacus: Explanation

The best path is [11, -4, 13], which sums to 20.

:brain: Kadane’s Algorithm: The Secret Spell

This efficient algorithm walks the path just once (O(n)) and keeps track of:

  • current_sum: current running total (reset if it drops below 0)
  • max_sum: highest sum encountered

:technologist: C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> arr(n);
        for (int i = 0; i < n; i++) cin >> arr[i];

        int current_sum = 0, max_sum = 0;
        for (int i = 0; i < n; i++) {
            current_sum += arr[i];
            if (current_sum < 0) current_sum = 0;
            max_sum = max(max_sum, current_sum);
        }

        cout << max_sum << endl;
    }
    return 0;
}

:hot_beverage: Java Implementation

import java.util.Scanner;

public class MaxSubsegmentSum {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

            int currentSum = 0, maxSum = 0;
            for (int num : arr) {
                currentSum += num;
                if (currentSum < 0) currentSum = 0;
                if (currentSum > maxSum) maxSum = currentSum;
            }

            System.out.println(maxSum);
        }
    }
}

:snake: Python Implementation

import sys

for line in sys.stdin:
    nums = list(map(int, line.strip().split()))
    if not nums:
        continue

    n = nums[0]
    arr = nums[1:]

    max_sum = 0
    current_sum = 0

    for num in arr:
        current_sum += num
        if current_sum < 0:
            current_sum = 0
        max_sum = max(max_sum, current_sum)

    print(max_sum)

:brain: Bonus Tip: When to Use Kadane’s Algorithm?

  • Competitive programming (like Codeforces, LeetCode, etc.)
  • Stock market profit ranges
  • Game level scoring analysis
  • Sensor reading optimization

:woman_fairy: Final Words from Arrayland

The adventurer walks away with the treasure worth 20 coins, thanks to your algorithmic wisdom. With Kadane’s magic in your toolbelt, you’re now ready to solve real-world optimization puzzles — one array at a time!