CODEWITHSUNDEEP
pythonarrayssub-array
Ammar Ahsan
Ammar Ahsan

Reputation: 51

To return subarray as well alongside maximum sum of subarray using kadane's algorithm

This code of mine returns maximum sum of subarray using kadane's algorithm. What changes can i do to this code to return the subarray corresponding to the maximum sum as well ?

def maxSubArray(a,size):
    curr_max=a[0]
    max_so_far=a[0]
    
    for i in a[1:]:
        curr_max=max(a[i],curr_max+a[i])
        max_so_far=max(max_so_far,curr_max)
    return max_so_far
a = [-2, -3, 4, -8, -2, 1, 5, -3] 
maxSubArraySum(a,len(a))

Upvotes: 1

Views: 516

Answers (1)

pakpe
pakpe

Reputation: 5489

Here is a solution that computes both the max sum and the corresponding contiguous subarray. It uses a single for loop with i. Then j trails i and is conditionally advanced. j and i help set the start and end indexes for the subarray that provides the max sum so far. At the end, the start and end indexes are used to slice the array and return the subarray.

def maxSubArraySum(a):
    max_so_far = 0
    current_max = 0
    start_index = 0
    end_index = 0
    j = 0 #trails i in the following loop. i and j help set start and end indexes

    for i in range(len(a)):
        current_max += a[i]

        if current_max > max_so_far:
            max_so_far = current_max
            start_index = j
            end_index = i

        # reset current max if negative and advance j
        if current_max < 0:
            current_max = 0
            j = i + 1

    result_array = a[start_index: end_index+1]
    print(f"Max sum is {max_so_far} for contiguous subarray: {result_array}")

maxSubArraySum([-2, -3, 4, -8, -2, 1, 5, -3])

#Output: Max sum is 6 for contiguous subarray: [1, 5]

Upvotes: 1

Related Questions