Kadane’s Algorithm is an amazing way to find the contiguous sub-array with maximum sum. This type of problem falls under Dynamic programming. So, we’re going to solve this problem using GeeksforGeeks requirement structure.

We have an array ‘arr’ of ‘N’ integers.

Input: The first line of input contains an integer T denoting the number of test cases.

• The first line contains a single integer N denoting the size of array.
• The second line contains N space-separated integers A1, A2, …, AN denoting the elements of the array.

Output: Print the maximum sum of the contiguous sub-array in a separate line for each test case.

`                                                       GeeksForGeeks link: Link`

#### SOLUTION BODY

``````def solution(nums):

for i in range(1, len(nums)):
if nums[i - 1] > 0:
nums[i] += nums[i - 1]

return max(nums)
``````

Execution Time: 0.4 seconds

#### INPUT BODY

``````def inputList(n):

while True:
print(f"Enter space separated elements of size {n}")
array = [int(num) for num in input().split()]
if len(array) == n:
break
else:
print("Entered value doesn't match with size N provided")

return array
``````

#### MAIN BODY

``````def main():
while True:
try:
T = int(input("Enter integer T denoting the number of test cases: "))
array = {}

for num in range(T):
N = int(input("Enter integer N denoting size of array: "))
array[num+1] = inputList(N)
print("")
sums = solution(array[num+1])

print(f"the maximum sum of the contiguous sub-array in {array[num+1]} is {sums}n")
break
except Exception as e:
print(e)
``````
``````main()
``````
```Enter integer T denoting the number of test cases: 2
Enter integer N denoting size of array: 5
Enter space separated elements of size 5 1 2 3 -2 5

the maximum sum of the contiguous sub-array in [1, 3, 6, 4, 9] is 9

Enter integer N denoting size of array: 4
Enter space separated elements of size 4 -1 -2 -3 -4

the maximum sum of the contiguous sub-array in [-1, -2, -3, -4] is -1```

Scripting