HackerRank

Point: not necessarily contigous max sub array, at least one element should be selected:

def maxSubarrCont(arr, n):
    ret = arr[0]
    curr = arr[0]
    for i in range(1, n):
        curr = max(arr[i], curr + arr[i])
        ret = max(ret, curr)    
    return ret

def maxSubarrNoCont(arr, n):    
    #    Corner case: no empty ret is allowed
    cnt = 0
    neg_max = -100001
    #
    ret = 0
    for i in range(0, n):
        d = max(0, arr[i])
        ret += d
        if d > 0: cnt += 1
        if arr[i] < 0:
            neg_max = max(neg_max, arr[i])
    if cnt == 0:
        return neg_max    
    return ret
    
T = input()
for i in xrange(T):
    N = int(input())
    arr = map(int, raw_input().split())
    print maxSubarrCont(arr, N), maxSubarrNoCont(arr, N)