Apply Kadane's technique: maintain a running total that resets to the current element whenever the running total drops below the current element's value.

Maximum Subarray

medium

Acceptance: 52%

Arrays

An integer array is given. Find a contiguous subarray (containing at least one element) that has the largest sum among all possible contiguous subarrays, and return that sum.

Examples

Example 1:

Input:nums = [3,-1,4,-2,5,-3,2]

Output:9

Explanation: The subarray [3,-1,4,-2,5] sums to 9, which is the maximum achievable.

Example 2:

Input:nums = [-4,-2,-8,-1]

Output:-1

Explanation: All values are negative. The best subarray is the single element -1.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Maximum Subarray

Examples

Hints

Related Problems