1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Alex
3 years ago
12

A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. For example, if S is 5,15,-30,10,-5,

40,10 then 5,15,-30 is a contiguous subsequence but 5,15,40 is not.
1. Give a linear-time algorithm for the following task:
Input: A list of numbers, A(1), . . . , A(n).
Output: The contiguous subsequence of maximum sum (a subsequence of length zero has sum zero).
For the preceding example, the answer would be 10,-5,40,10 with a sum of 55.
Computers and Technology
1 answer:
Sindrei [870]3 years ago
4 0

Answer:

We made use of the dynamic programming method to solve a linear-time algorithm which is given below in the explanation section.

Explanation:

Solution

(1) By making use of the  dynamic programming, we can solve the problem in linear time.

Now,

We consider a linear number of sub-problems, each of which can be solved using previously solved sub-problems in constant time, this giving a running time of O(n)

Let G[t] represent the sum of a maximum sum contiguous sub-sequence ending exactly at index t

Thus, given that:

G[t+1] = max{G[t] + A[t+1] ,A[t+1] } (for all   1<=t<= n-1)

Then,

G[0] = A[0].

Using the above recurrence relation, we can compute the sum of the optimal sub sequence for array A, which would just be the maximum over G[i] for 0 <= i<= n-1.

However, we are required to output the starting and ending indices of an optimal sub-sequence, we would use another array V where V[i] would store the starting index for a maximum sum contiguous sub sequence ending at index i.

Now the algorithm would be:

Create arrays G and V each of size n.

G[0] = A[0];

V[0] = 0;

max = G[0];

max_start = 0, max_end = 0;

For i going from 1 to n-1:

// We know that G[i] = max { G[i-1] + A[i], A[i] .

If ( G[i-1] > 0)

G[i] = G[i-1] + A[i];

V[i] = V[i-1];

Else

G[i] = A[i];

V[i] = i;

If ( G[i] > max)

max_start = V[i];

max_end = i;

max = G[i];

EndFor.

Output max_start and max_end.

The above algorithm takes O(n) time .

You might be interested in
What are tributaries
sukhopar [10]
Tributaries are rivers that flow into another river or another lake. Tributaries are common in any country. Tributaries are like roots of lakes that flows to somewhere else. It is like a distribution of water that scatters through streams and lands to a larger body of water.
5 0
3 years ago
Read 2 more answers
What type of task can be defined to allow you fine-grained control over the management tasks a user can perform in an OU
erma4kov [3.2K]

The type of task can be defined to allow you fine-grained control over the management tasks a user can perform in an OU is custom.

<h3>What is custom priority in Outlook tasks?</h3>

Outlook is known to have a  New Tasks window that often shows a created-in Priority field that has  Low, Normal, and High setting.

This setting above is a custom one and it is one where a person can sort tasks by using its priority level instead of due date. This help to have  more perspective and one can reorganize their tasks when needed.

Learn more about task  from

brainly.com/question/12831236

3 0
2 years ago
Write two statements to read in values for birthMonth followed by birthYear, separated by a space. Write a statement to print th
Ede4ka [16]

Answer:

// here is code in the C++.

#include <bits/stdc++.h>

using namespace std;

// main function

int main() {

// variable to store the input

int birth_month,birth_year;

cout<<"enter birth month:";

// read the birth month

cin>>birth_month;

cout<<"enter birth year:";

// read the birth year

cin>>birth_year;

// print the output

cout<<birth_month<<"/"<<birth_year<<endl;

return 0;

}

Explanation:

Declare two variables to store the birth month and birth year.Read the inputs from the user and assign it the variables.Print the birth month and year separated by a slash "/".

Output:

enter birth month:1                                                                                                        

enter birth year:2000                                                                                                      

1/2000

5 0
3 years ago
When listing columns in the select list, what should you use to separate the columns?
Gala2k [10]
The answer is commas.  <span>When listing columns in the select list, commas should be used to separate the columns.</span>
6 0
3 years ago
When I use
slega [8]

Answer:

If it works then no, if it doesn't then yes

Explanation:

Code Academy probably runs either way because it is not taking this as a intense class.

5 0
3 years ago
Other questions:
  • Fill in the blank.
    7·1 answer
  • Which of the following is NOT a safe skill you can use to reduce your risk
    11·2 answers
  • Write a program that receives an character and displays its Unicode. Here is a sample run: Enter an character: E The Unicode for
    8·1 answer
  • I used the app and my answers were still wrong??????how
    8·2 answers
  • I NEED HELP ASAP
    8·1 answer
  • What is an information technology? ​
    12·2 answers
  • Lets say if my computer shut down every 10 minutes. What can you do to solve the problem. Hint: Use these word in you answer: ha
    10·2 answers
  • What is the output?
    11·1 answer
  • How can Technology be used in marketing?
    5·1 answer
  • What are logic gates ?​
    10·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!