Show the optimal substructure

Assignment Help Basic Computer Science

Reference no: EM131123200

Suppose you are given an array of n integers a1, a2, ..., an. You need to find out the length of its longest sub-array (not necessarily contiguous) such that all elements in the sub-array are sorted in non-decreasing order. For example, the length of longest sub-array for { 5, 10, 9, 13, 12, 25, 19, 70, 80 } is 6 and one such sub-array is {5, 10, 13, 19, 70, 80}. Note you may have multiple solutions for this case. Use dynamic programming to solve this problem. Your solution need to show:

1) the optimal substructure;

2) the pseudo code of your solution and its complexity; and

3) a few examples how your approach works. In cases where there are multiple longest sub-arrays, you just need to show one of them.

Reference no: EM131123200

Questions Cloud

What psychiatric disorder is roommate attributing to sue : You're studying for your upcoming psychology exam when your roommate breezes in, saying: What psychiatric disorder is your roommate attributing to Sue? How is this different from schizophrenia

Confidence interval estimate of the expected value : a. Estimate the standard deviation ofwhenx= 8. b. Develop a 95% confidence interval estimate of the expected value ofywhenx= 8.

Currently enrolled in business statistics : Of 300 business students, 100 are currently enrolled in accounting and 80 are currently enrolled in business statistics. These enrollment figures include 30 students who are in fact enrolled in both courses.

How could you explain the behavior of mary fiance : When your family gathers for Thanksgiving, your cousin Mary brings her new fiancé; it's the first time he's met the whole family, and his behavior is a little strained: How could you explain the behavior of Mary's fiancé using situational attribut..

Show the optimal substructure : a few examples how your approach works. In cases where there are multiple longest sub-arrays, you just need to show one of them.

To investigate the effect of management training : Management Training An experiment was conducted to investigate the effect of management training on the decision-making abilities of supervisors in a large corporation. Sixteen supervisors were selected, and eight were randomly chosen to receive m..

Essay discussing the jockey club powerful influence : 350 word essay discussing two examples to illustrate the Jockey Club's powerful influence over French Opera

What are the ethical issues raised by this procedure : Compare your reactions to that procedure with your reactions to an analogous one in which people are given false feedback that they possess a very favorable personality trait or a very high ability level.

Essay explaining how the great fire of london can be viewed : 350 word essay explaining how the great fire of London can be viewed as both a curse and a blessing

User Account

All Pages