#!/usr/bin/env python
# coding: utf-8

# # Contiguous Subarray
# Largest Sum Contiguous Subarray

# ## Kadane's Algorithm - Dynamic Programming - O(n)

# In[1]:


def largeSumContiguousSubArr(arr):
    start, end = 0, 0
    s = 0
    max_so_far, curr_max = 0, 0
    
    for i in range(len(arr)):
        curr_max += arr[i]
        
        if curr_max < 0:
            curr_max = 0
            s = i + 1
        elif curr_max > max_so_far:
            max_so_far = curr_max
            start = s
            end = i
            
    return arr[start : end + 1], max_so_far


# In[2]:


arr = [-2, -3, 4, -1, -2, 1, 5, -3]
arr


# In[3]:


largeSumContiguousSubArr(arr)