CODEWITHSUNDEEP
pythonalgorithm
Pierre-Alexandre
Pierre-Alexandre

Reputation: 775

Return left and right index of maxsubarray

Given a list of numbers, I am trying to find the left and right index of the maximum subarray such as for [-1, 9, 0, 8, -5, 6, -24] the maximum subarray will be [9, 0, 8, -5, 6] so the return should be [1, 5]

def max_profit(data):
  max_sum = 0
  max_right_index = 0
  max_left_index = 0
  current_sum = 0
  for i in data: 
    current_sum = current_sum + i
    if current_sum < 0:
      current_sum = 0
    if max_sum < current_sum:
      max_sum = current_sum
      max_right_index = i  
  return [max_left_index, max_right_index -1]

What would be the best startegy to get the right index?

Upvotes: 0

Views: 221

Answers (2)

Hithru
Hithru

Reputation: 66

My approach was to keep the track of minimum subarray and the continuous sum of subarray starting from the beginning and using that we can find the maximum subarray start and end index since the start index will be end of minimum subarray + 1 (only if minimum subarray is negative)

def max_subarray(arr):
    maximum_subarray_sum = -float('inf')
    maximum_value = -float('inf')
    maximum_value_index = None
    no_positive_value = True

    continues_subarray_sum = 0
    minimum_subarray_sum = 0
    minimum_subarray_end_index = -1

    maximum_subarray_start_index = 0
    maximum_subarray_end_index = 0

    for i in range(len(arr)):

        if arr[i] >= 0:
            no_positive_value = False
        if arr[i] > maximum_value:
            maximum_value = arr[i]
            maximum_value_index = i

        continues_subarray_sum += arr[i]
        if continues_subarray_sum < minimum_subarray_sum:
            minimum_subarray_sum = continues_subarray_sum
            minimum_subarray_end_index = i

        current_highest_subarray_sum = continues_subarray_sum - minimum_subarray_sum

        if current_highest_subarray_sum > maximum_subarray_sum:
            maximum_subarray_sum = current_highest_subarray_sum
            maximum_subarray_start_index = minimum_subarray_end_index + 1
            maximum_subarray_end_index = i

    if no_positive_value:
        return [maximum_value, maximum_value_index, maximum_value_index]
    else:
        return [maximum_subarray_sum, maximum_subarray_start_index, maximum_subarray_end_index]


print(max_subarray([2, -1, 2, 3, 4, -5]))
print(max_subarray([-1, 9, 0, 8, -5, 6, -24]))

Upvotes: 1

Sakib Md Al Amin
Sakib Md Al Amin

Reputation: 334

What does i indicate, the index you're currently at or the value you're trying to sum up? Looks like you messed them up here: current_sum = current_sum + i & max_right_index = i.

Anyways, the solution is well known as Kadane’s Algorithm, check this out: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

Upvotes: 1

Related Questions