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?

CodePudding user response：

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/

CodePudding user response：

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]))