O(n^2)??

Dark Mode

Piyush mishra
asked
in Algorithms
Jan 2, 2019

267 views
0 votes

Given a sequence of n real numbers a1,a2,a3,a4…………...an then to find contiguous subsequence Ai,Ai+1,…...Aj.such that its sum is maximum.

How much time the above problem will take if you dynamic program?

How much time the above problem will take if you dynamic program?

It can be done in O(n) time by using Kadane's algorithm.

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

0