Dynamic programming

shipra tressa asked in Algorithms Jul 17, 2018 retagged Jun 18, 2022 by makhdoom ghaya

1,475 views

0 votes

Given a sequence of n real numbers a1,a2,a3...an then to find contiguous subsequence ai,ai+1,ai+2....aj. Such that it's sum is maximum. How much time the above problem will take if you use dynamic programming?

dynamic-programming
time-complexity

shipra tressa asked in Algorithms Jul 17, 2018 retagged Jun 18, 2022 by makhdoom ghaya

by shipra tressa

1.5k views

0 Comments

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

1 vote

time complexity=O(n)

space complexity=O(n)(we can improve it to O(1))

https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

Anil Ji answered Jul 17, 2018

by Anil Ji

0 Comments

Please log in or register to add a comment.

← Previous Next →

← Previous in category Next in category →

Related questions

1 vote

1 answer

Na462 asked in Algorithms Jun 29, 2018

1,445 views

Ace Test Series: Algorithms - Dynamic Programming OBST

Na462 asked in Algorithms Jun 29, 2018

by Na462

1.4k views

ace-test-series
algorithms
dynamic-programming
time-complexity

0 votes

1 answer

Rohit Pandey asked in Algorithms Jun 28, 2018

351 views

Dynamic programming
Consider the following C functions: int fun ( int n) { if (n<6) return 1; else return( fun(n-1)+fun(n-3)+fun (n-5)); } Q) Suppose we modify the above function fun( ) and store the values of fun (i), 0<=i<n, as and when they are computed . With this ... ( ) is significantly reduced. What is the time complexity of modified fun( ) would be: a)O(1) b)O(n) c)O(n^2) d)O(n!)

Rohit Pandey asked in Algorithms Jun 28, 2018

by Rohit Pandey

351 views

algorithms
dynamic-programming
time-complexity

4 votes

1 answer

Aditi Tiwari asked in Algorithms Dec 22, 2015

1,243 views

Dynamic programming
Given an array which contains both positive and negative integers in it and asked to design an algorithm to find the maximum sum which does not contain two consecutive numbers.What is the time comlexity of efficient algorithm A) Θ(nlogn) B) Θ(n) C) Θ(n2) D) Θ(n2logn)

Aditi Tiwari asked in Algorithms Dec 22, 2015

by Aditi Tiwari

1.2k views

algorithms
dynamic-programming
time-complexity

0 votes

0 answers

Sahil_Lather asked in Algorithms Jan 28, 2023

359 views

TestBook testSeries dynamic programming and np problem question
Consider the following statements, which of the statement(s) is/are FALSE? The running time of dynamic programming algorithm is always θ (p) where p is number of subproblems When a recurrence relation has cyclic dependency, it is ... memorization If a problem X can be reduced to a known NP hard problem, then X must be NP-hard

Sahil_Lather asked in Algorithms Jan 28, 2023

by Sahil_Lather

359 views

algorithms
dynamic-programming
testbook-test-series

Subscribe to GATE CSE 2024 Test Series

Subscribe to GO Classes for GATE CSE 2024

Quick search syntax

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Subjects

All categories
General Aptitude (3.5k)
Engineering Mathematics (10.4k)
Digital Logic (3.6k)
Programming and DS (6.2k)
Algorithms (4.8k)
Theory of Computation (6.9k)
Compiler Design (2.5k)
Operating System (5.2k)
Databases (4.8k)
CO and Architecture (4.0k)
Computer Networks (4.9k)
Artificial Intelligence (79)
Machine Learning (48)
Data Mining and Warehousing (25)
Non GATE (1.4k)
Others (2.7k)
Admissions (684)
Exam Queries (1.6k)
Tier 1 Placement Questions (17)
Job Queries (80)
Projects (11)
Unknown Category (870)

64.3k questions

77.9k answers

244k comments

80.0k users

Recent Blog Comments

category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...

Send feedback
Rank Predictor
College Prediction
Useful Links
FAQ
Corrections
Discuss
Copyright
Request
Testimonials
Chat Logs
Chat
Badges
Search tips
Exam Category
Blog Category
Blog Tags
Privacy
Test Series
GATER
Refund Policy
Terms and Conditions
Contact Us

Developed by Chun

Dynamic programming

0 Comments

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

0 Comments

Please log in or register to add a comment.

Related questions

Subscribe to GATE CSE 2024 Test Series

Subscribe to GO Classes for GATE CSE 2024

Recent Posts

Subjects

Recent Blog Comments