max_sum.java

package com.example.helloworld;

// Implement a function that calculates the max consecutive sum on a subsequence of integers.
// What is the maximum sum one can achieve by summing consecutive numbers on a finite array of positive
// and negative numbers? One can start and end anywhere, but it is not allowed to skip numbers.
//
// For example, consider the array [2, -4, 2, -1, 3, -3, 10, -1, -11, -100, 8, -1].
// The max possible consecutive sum is 11 (starting from the index 2 and ending with the index 6, both zero-based).

// sum = 9
// 2
// -4 = -2
// 2 = 0
// -1 = -1
// 3 = 2
// -3 = -1
// 10 = 9
// -1 = 8
// -11 = -3
// -100 = -103
// 8 = -95
// -1 = -96

// [11, -3, -2]
// 11 = 11
// 11 + -3 = 8
// 11 + (-3) + (-2) = 5

import java.util.Arrays;
import java.util.List;

public class HelloWorld {

    public static int maxSum(List<Integer> numbers) {
        int sum = 0;

        for (int i = 0; i < numbers.size(); i++) {
            sum = 0;
            for (int j = i; j < numbers.size(); j++) {
                if (sum + numbers.get(j) >= sum) {
                    sum = sum + numbers.get(j);
                }
            }
        }

        return sum;
    }

    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(2, -4, 2, -1, 3, -3, 10, -1, -11, -100, 8, -1);
        System.out.println("Max: " + maxSum(numbers));
    }
}