Largest sum contiguous subarray

The problem you're referring to is often known as the "Maximum Subarray Problem". It involves finding the contiguous subarray within a one-dimensional array of numbers (containing both positive and negative numbers) that has the largest sum.

Here's a simple algorithm to solve this problem using Kadane's algorithm:

public class MaximumSubarray {

    public static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;

        int maxSum = nums[0];
        int currentSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum sum of contiguous subarray: " + maxSubArray(nums));
    }
}

This code defines a method maxSubArray which takes an array of integers as input and returns the sum of the maximum contiguous subarray. The maxSubArray method iterates through the array, updating currentSum to either the current element or the sum of the current element and the previous sum (whichever is larger). At each step, maxSum is updated to store the maximum sum found so far. Finally, the maximum sum is returned.