find subarray with maximum sum code example

Example 1: kadane algorithm

public int kadane(int[] arr){
	int max_so_far = 0, curr_max = Integer.MIN_VALUE;
    for(int i: arr){
    	max_so_far += i;
        if(max_so_far<0) max_so_far = 0;
        if(max_so_far>curr_max) curr_max = max_so_far;
    }
    return curr_max;
}

Example 2: find longest subarray by sum

def max_length(s, k):
    current = []
    max_len = -1 # returns -1 if there is no subsequence that adds up to k.
    for i in s:
        current.append(i)
        while sum(current) > k: # Shrink the array from the left, until the sum is <= k.
           current = current[1:]
        if sum(current) == k:
            max_len = max(max_len, len(current))

    return max_len

Example 3: max subsequence sum in array

def max_subarray(numbers):
    """Find the largest sum of any contiguous subarray."""
    best_sum = 0  # or: float('-inf')
    current_sum = 0
    for x in numbers:
        current_sum = max(0, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum