Question

We are given an array A of size n containing n positive and negative integers (the array is indexed starting from 0).

Our goal is to find two indices i and j such that 0 ≤ i ≤ j ≤ n and Pk=j k=i A[k] is maximized.

Input sequence: [2, -4, 1, 9, -6, 7, -3]

Output: [1, 9, -6, 7] or i = 2 and j = 5

Input sequence: [1, 2, 3, 4, 5, 6, -3]

Output: [1, 2, 3, 4, 5, 6] or i = 0 and j = 5 Y

ou do not have to output the resulting subarray, just the two indices i and j.

Design an O(n 3 )-time iterative algorithm to solve the problem. Give pseudo-code and a short description. Design an O(n 2 )-time iterative algorithm to solve the problem. Give pseudo-code and a short description.

Answer 1

(1): O(n³) algorithm for above problem is as follows:

function max_sub_array(lst):
   len=lst.length
   max_sum=0
   max_sum_i=0
   max_sum_j=0
   for i=0 to len-1:
       for j=i to len-1:
           sum=0
           for k=i to j:
               sum+=lst[k]
           if sum>max_sum:
               max_sum=sum
               max_sum_i=i
               max_sum_j=j
   return (max_sum_i,max_sum_j)

Explanation:

Here, we traverse all subarrays which takes O(n²) time and inside it, we add sum of all elements of subarray which takes O(n) in worst case. So time complexity of this algorithm is O(n³)

(2): O(n²) algorithm for above problem is as follows:

function max_sub_array(lst):
   len=lst.length
   max_sum=0
   max_sum_i=0
   max_sum_j=0
   for i=0 to len-1:
       sum=0
       for j=i to len-1:
           sum+=arr[j]
           if sum>max_sum:
               max_sum=sum
               max_sum_i=i
               max_sum_j=j
   return (max_sum_i,max_sum_j)

Explanation:

Here, we traverse all subarrays which takes O(n²) time and here we maintain sum of subarray using sum variable. So time complexity of this algorithm is O(n²) in worst case.

Mention in comments if any mistakes or errors are found. Thank you.