def max_subarray(nums):
    """
    Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

    For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
    the contiguous subarray [4,-1,2,1] has the largest sum = 6.

    Args:
        nums: list[int]

    Returns:
        int

    """

    # Method 1 Kadane Algorithm
    max_so_far = max_end_here = nums[0]

    for x in nums:
        #  DP, optimal substructure:
        max_end_here = max(max_end_here + x, x)  # max_end_here[i] = max(max_end_here[i - 1] + nums[i], nums[i])
        max_so_far = max(max_so_far, max_end_here)  # max_so_far[i] = max(max_so_far[i-1], max_end_here[i])

    return max_so_far