7. Jack Ostrich, a notorious pirate, has come across a single-file convoy of mer
ID: 3732331 • Letter: 7
Question
7. Jack Ostrich, a notorious pirate, has come across a single-file convoy of merchant ships that he would like to plunder. Some of these ships, however, are well defended, and the cost of repairing Jack's ship, the Blue Pearl, after engaging them would amount to more than their treasure is worth. Further complicating measures is the fact that, while Jack can choose any point in the convoy to break off, he cannot return after doing so, and must engage each ship in the convoy up to that point. For example, consider the following convoy: 5 6-9 2-8 4 -7 3 -5 Then, breaking off the convoy after the second ship would be the best option, as it yields a net profit of 11 (which is the highest possible given this convoy). Assuming that Jack has already calculated the cost or benefit to plundering each merchant ship: (a) Give an O(n) algorithm that will let him walk away with the maximum net profit. (b) Suppose Jack has hired an expert navigator, and can now choose an interception point as well as a breakoff point. Give an O(n * log(n)) algorithm that makes the best use of his new ability.Explanation / Answer
Q1. O(n)
All arrays are 1 indexed.
arr[n] - array of profits and losses of each ship
First we find the sum of all elements before an element and store it in array c.
Then the maximum sum of subarray is the greatest element in c.
begin
read arr[n]
int c[n]
c[1]=arr[1]
for i= 2 -> n
{
c[i]=c[i-1]+arr[i]
}
int max=c[1]
int max i=1
for i= 2 -> n
{
if(c[i]>max)
{
max=c[i]
maxi=i
}
}
return maxi
Q2. O(n.logn)
To get nlogn running time we will use divide and conquer algorithm.
In short what it does is that it returns the maximum of the following three
a)Maximum subarray sum of left half of array (find recursively)
b)Maximum subarray sum of right half of array (find recursively)
c)Maximum sum subarray that passes through middle
The variables used are:
maxl=Maximum subarray sum of the left half
maxli=the left index corresponding to maxl
maxlj=the right index corresponding to maxl
maxr=Maximum subarray sum of the right half
maxri=the left index corresponding to maxr
maxrj=the right index corresponding to maxr
cenmax=Maximum subarray sum which passes through middle
cenmaxl= sum corresponding to the left half of cenmax
cenmaxr= sum corresponding to the right half of cenmax
cenmaxi=the left index corresponding to cenmax
cenmaxj=the right index corresponding to cenmax
The findmax() function returns the maximum subarray sum,its left index and also its right index.
It is called with findmax(arr,1,n)
begin
read arr[n]
return findmax(arr,1,n)
FINDMAX SUBROUTINE
findmax(arr,i,j)
{
mid=(i+j)/2
[maxl,maxli,maxlj]=findmax(arr,i,mid)
[maxr,maxri,maxrj]=findmax(arr,mid+1,j)
cenmaxl=0
for p= mid -> i
{
if(cenmaxl+arr[p]<0)
break
else
{
cenmaxl=cenmal+arr[p]
cenmaxi=p
}
}
cenmaxr=0
for p= mid+1 -> j
{
if(cenmaxr+arr[p]<0)
break
else
{
cenmaxr=cenmaxr+arr[p]
cenmaxj=p
}
}
cenmax=cenmaxl+cenmaxr
if maxl is greater than cenmax and maxr
return maxl,maxli and maxlj
if maxr is greater than cenmax and maxl
return maxr,maxri and maxrj
else
return cenmax,cenmaxi,cenmaxj
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.