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 ^{3}) 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^{2})
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^{3})

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

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

Divide-and-Conquer technique is famous for providing O(n log n)
solutions for problems with O(n2) straight forward
solutions. One of those problems is the “Maximum Subarray Sum” or
“Maximum Value Contiguous Subsequence": Given a sequence of n
numbers A[0 ... n-1], give an algorithm for finding a contiguous
subsequence A[i ... j], for which the sum of elements in this
subsequence is the maximum we can get by choosing different i or
j.
For example: the maximum subarray sum for the...

1. Given an
n-element array A, Algorithm X executes an
O(n)-time computation for each even
number in A and an O(log n)-time computation for
each odd number in A.
What is the best-case running time of Algorithm X?
What is the worst-case running time of Algorithm X?
2. Given an array,
A, of n integers, give an O(n)-time algorithm that finds
the longest subarray of A such that all the numbers in that
subarray are in sorted order. Your algorithm...

Q2) (1 point) Given two lists, L1 of length n and L2 of length
m. We say that L2 is a subsequence of L1 if we can remove elements
from L1 to produce L2. This means that there exists indices i1 <
... < im such that L1[ij] = L2[j] for each j. Design an
algorithm that detects if L2 is a subsequence of L1 and outputs the
indices i1,....,im if L2 is a subsequence of L1.
a.Provide the pseudo-code...

How to measure the time complexity of an
algorithm?
Identify an important operation in the algorithm that is
executed most frequently.
Express the number of times it is executed as a function of
N.
Convert this expression into the Big-O notation.
A. For each of the three fragments of code, what is its
worst-case time complexity, in the form "O(…)". (Use the
given solution to the first problem as a
model)
//----------------- This is a sample problem – solved
------...

A Queue is a linked list with pointers to both the head of the
list as well as the tail (or the last element) of the list. Given a
queue Q, Q.head gives the head of the queue and Q.tail gives the
tail of the queue. Give O(1) time algorithms for the following
tasks. Enqueue • Input: A queue Q of distinct integers and a queue
element a not in Q. 1 • Output: Q with the element a added...

Write a function
called TaylorSin.m that takes as input an array x, and positive
integer N, and returns the Nth Taylor polynomial approximation of
sin(x), centered at a = 0. The first line of your code should
read
function s =
TaylorSin(x,N)
HINT: in computing k!,
use kfact = k*(k-1)*kfact since you are counting by 2

Write an application in Java which includes an algorithm that
takes an array of any size, selects the high and low integer from
the array of integers with each pass and builds a new array of
integers by inserting the high and low selection with each pass.
Your output should show the original array of integers and the
output of each pass on a new line.
Note: You can assume all integers are positive, but your
code must work for...

Answer the questions based on the program given below.
a) Write the function prototype of fnFunny function.
b) Write the output produced by the above program
#include <stdio.h>
int main (void){
unsigned short i =4;
unsigned long j = 6 ;
short k = 2 ;
k = fnFunny ( i , j );
printf("i = %hu, j = %lu, k =
%hi\n", i, j, k);
return 0;
}
short fnFunny (unsigned short i,...

Please code in Java and please implement constarints Digital
Root and Iterations Given a non-negative integer, print out its
digital root and the number of iterations required to reach it. The
digital root is the single digit number obtained by an iterative
process of finding the sum of digits. In the next iteration, the
sum of the digits in the previous iteration is computed, and the
process repeated until a single digit value is obtained. Input
Format The first line...

CountingSort(A, B, k)
for i=1 to k
C[i]= 0;
for j=1 to n
C[A[j]] += 1;
for i=2 to k
C[i] = C[i] + C[i-1];
for j=n downto 1
B[C[A[j]]] = A[j];
C[A[j]] -= 1;
illustrate the operation of COUNTING-SORT on the array A =
{6,0,2,0, 1, 3, 5, 6, 1, 3, 2}. Specifically, show the four arrays
A, B, C, and C'.

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 13 minutes ago

asked 13 minutes ago

asked 13 minutes ago

asked 22 minutes ago

asked 28 minutes ago

asked 32 minutes ago

asked 39 minutes ago

asked 44 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago