Answered: 2a. Provide a divide-and-conquer…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

2a. Provide a divide-and-conquer algorithm that will determine the maximum sum possible for a subarray of a given array. The array only contains the values 1, -1 and -2. [Adapted from IOA, Ch. 4] Example input: 1 -2 1 1 1 1 -1 1 1

Expert Solution

Source Code

def maxSum(arr, l, m, h):

sum_el = 0
left_sum = -10000

for i in range(m, l-1, -1):
sum_el = sum_el + arr[i]

if (sum_el > left_sum):
left_sum = sum_el

sum_el = 0
right_sum = -1000
for i in range(m + 1, h + 1):
sum_el = sum_el + arr[i]

if (sum_el > right_sum):
right_sum = sum_el

return max(left_sum + right_sum, left_sum, right_sum)

def maxSumSubArray(arr, l, h):

if (l == h):
return arr[l]

m = (l + h) // 2

return max(maxSumSubArray(arr, l, m),
maxSumSubArray(arr, m+1, h),
maxSum(arr, l, m, h))

arr = [1,-2,1,1,1,1,-1,1,1]
n = len(arr)

max_sum = maxSumSubArray(arr, 0, n-1)
print("Maximum consecutive sum is ", max_sum)

Step by step

Solved in 3 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Fundamentals of Multithreaded Algorithms

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions