Question

# We are given an array A of size n containing n positive and negative integers (the...

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.

(1): O(n3) 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(n2) 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(n3)

(2): O(n2) 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(n2) time and here we maintain sum of subarray using sum variable. So time complexity of this algorithm is O(n2) in worst case.

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