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
2 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]2 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 type of hard drive is in original xbox?
castortr0y [4]
The original Xbox had an 8GB hard disk drive, or HDD.

You basically gave yourself the answer! A hard drive.
4 0
3 years ago
In java write a program:A contact list is a place where you can store a specific contact with other associated information such
BigorU [14]

Answer:

import java.util.Scanner;

public class ContactInformation

{

public static String GetPhoneNumber(String[] nameVec, String[] phoneNumberVec, String contactName, int arraySize)  

{  

for(int i=0;i<arraySize;i++)

{

if(nameVec[i].equals(contactName))  

return phoneNumberVec[i];

}  

return "Contact doesn't exists!";

}

public static void main(String[] args)

{

int records;

Scanner sc = new Scanner(System.in);

System.out.print("Enter the size of contact List :");

records=sc.nextInt();

String[] contactNameList=new String[records];

String[] phoneNumberList=new String[records];

String contactName;

System.out.println("Enter the contact name and phone number :");

for(int i=0;i<contactNameList.length;i++)

{  

contactNameList[i]=sc.next();  

phoneNumberList[i]=sc.next();  

}  

System.out.println("Enter the name of the contact to be searched :");  

contactName=sc.next();

System.out.println(GetPhoneNumber(contactNameList,phoneNumberList,contactName,records));  

}  

}

Explanation:

In the following the function defined above for getting the contact

number on the basis of contact number provided we are checking the contact name list if we are able to find the contact name and if we did we return the contact number on the same index from the contact number list

which we found in the contact name list.

4 0
3 years ago
Polymorphism means (Points : 2) many forms
Pavel [41]

Answer:

many forms

Explanation:

Polymorphism is a construct in object oriented programming which means multiple forms.For example: Suppose I have a function which performs the add operation on two integers and another function with the same name which concatenates 2 given strings:

  • int add ( int a, int b);
  • string add ( string a , string b)

The two functions represent polymorphic forms of the add function. The function to be invoked at runtime is determined by the runtime argument type.

For example , add (2,3) will invoke int add ( int a, int b);

Similarly, add("hello","world") will invoke string add ( string a , string b);

6 0
3 years ago
Define the computer with its workintg principple
GenaCL600 [577]

Explanation:

Computer is an electronic device that is designed to work with information.

WORKING PRINCIPLE OF COMPUTER

a.It accepts data and instructions by way of input,

b.It stores data,

c.It can process data as required by the user,

d.It gives result in the form of output,

e.It controls all operations inside a computer.

I hope it will help you

5 0
2 years ago
One or more messages about the same topic is a ?
elena55 [62]

Answer:

This is the case of redundancy or the repeated data. It means that the same data is being repeated again and again. And its the wastage of time and memory both. The redundancy must be removed in all circumstances. However, we cannot as without it proper normalization of data is not possible.

Explanation:

The answer is self explanatory.

6 0
3 years ago
Other questions:
  • Which three phrases describe a wireframe
    12·1 answer
  • How is the Task Manager helpful in displaying which resources your computer is using and how fast?
    5·2 answers
  • USB keys can store terabytes of data. Of the five key factors that contribute to the increasing vulnerability of organizational
    13·1 answer
  • You are in charge of five software development projects. The project characteristics of each of the sys are as follows:
    13·1 answer
  • Okay so remember that page I was advertising? At: fol ? Now it's deleted. And idk why because I was doing everything the right w
    7·1 answer
  • 9. What is composition? Why is composition important?
    11·1 answer
  • You are in charge of an event at work. You want to plan and schedule events and resourse. What type of software should you use?
    14·2 answers
  • What is the decrypted binary
    9·1 answer
  • Space cushion includes
    8·2 answers
  • True or False? Security code is almost always open source!<br> True<br> False
    8·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!