blocks|key|1505118|text|这不是动态规划，它是一个蛮力的解决方案。解决方案似乎是正确的，但正如你所观察到的-它是低效的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1505119|一个O(n)解决方案可以通过应用动态规划来实现，将D(i)表示为以i结尾的最大子连续子数组，并且必须包括i。|offset|length|style|CODE|1505120|D(-1)+=+0
D(i)+=+max{+arr[i],+D(i-1)|code-block|syntax|javascript|1505121|这样做的想法是，您有两个选择--获得以i-1结尾的“最佳”数组并将元素i添加到其中，或者创建一个以i开头的新数组。|1505122|最后，通过在DP解决方案中应用上面的内容，您可以得到一个数组，其中每个元素都表示以该索引结尾的最大次连续数组，您所要做的就是从这个数组中选择最大值来得到最大和的值，然后回到数组上得到实际的子序列。|1505123|示例：|BOLD|1505124|array+=+5,15,-30,10,-5,40,10|1505125|应用动态规划：|1505126|D(-1)+=+0
D(0)+=+5
D(1)+=+20
D(2)+=+-10
D(3)+10+//because+max{-10%2B10,10}+=+10
D(4)+=+5
D(5)+=+45
D(6)+=+55|1505127|现在你有了数组：|1505128|D+=+[5,20,-10,10,5,45,55]|1505129|最大子序列的值为55，由[10,-5,40,10]给出(按照上面的数组，然后返回)|1505130|entityMap^0|0|P|4|X|1|1G|1|0|0|J|3|Z|1|1D|1|0|0|0|3|0|0|0|0|0|0|C|D|0^^$0|@$1|2|3|4|5|6|7|17|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|18|8|@$D|19|E|1A|F|G]|$D|1B|E|1C|F|G]|$D|1D|E|1E|F|G]]|9|@]|A|$]]|$1|H|3|I|5|J|7|1F|8|@]|9|@]|A|$K|L]]|$1|M|3|N|5|6|7|1G|8|@$D|1H|E|1I|F|G]|$D|1J|E|1K|F|G]|$D|1L|E|1M|F|G]]|9|@]|A|$]]|$1|O|3|P|5|6|7|1N|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1O|8|@$D|1P|E|1Q|F|S]]|9|@]|A|$]]|$1|T|3|U|5|J|7|1R|8|@]|9|@]|A|$K|L]]|$1|V|3|W|5|6|7|1S|8|@]|9|@]|A|$]]|$1|X|3|Y|5|J|7|1T|8|@]|9|@]|A|$K|L]]|$1|Z|3|10|5|6|7|1U|8|@]|9|@]|A|$]]|$1|11|3|12|5|J|7|1V|8|@]|9|@]|A|$K|L]]|$1|13|3|14|5|6|7|1W|8|@$D|1X|E|1Y|F|G]]|9|@]|A|$]]|$1|15|3|-4|5|6|7|1Z|8|@]|9|@]|A|$]]]|16|$]]

This is not Dynamic Programming, it is a brute force solution. The solution seems to be correct, but as you observer - it is inefficient.

An O(n) solution can be achieved by applying Dynamic Programming, denote <code>D(i)</code> as the maximum sub contiguous subarray that ends in <code>i</code>, and must include <code>i</code>.

<pre><code>D(-1) = 0
D(i) = max{ arr[i], D(i-1)
</code></pre>

The idea is, you have two choices - get the previously "best" array that ends at <code>i-1</code> and add element <code>i</code> to it, or create a new one that starts with <code>i</code>.

At the end, by applying the above in a DP solution, you get an array where each element indicates the maximum sub contiguous array ending with this index, all you have to do is choose the maximal value out of this array to get the value of the maximal sum, and go back on the array to get the actual subsequence.

<hr>

Example:

<pre><code>array = 5,15,-30,10,-5,40,10
</code></pre>

Applying the dynamic programming:

<pre><code>D(-1) = 0
D(0) = 5
D(1) = 20
D(2) = -10
D(3) 10 //because max{-10+10,10} = 10
D(4) = 5
D(5) = 45
D(6) = 55
</code></pre>

And now you have the array:

<pre><code>D = [5,20,-10,10,5,45,55]
</code></pre>

The maximal subsequence's value is 55, and is given by <code>[10,-5,40,10]</code> (following the above array, and going back on it)

blocks|key|1505175|text|基本上是再次计算和，again.You可以通过将和存储在数组中来避免这种情况。你可以用O(n)来做。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1505176|设S0，1.n-1是序列设T0,1，.n-1是从i元开始的最大连续和。|1505177|现在要填充Ti，从相反开始。Tn-1=最大值(Sn-1，0)|1505178|现在Ti=max(Ti%2B1%2BSi，Si+,0)|1505179|现在，遍历'T‘数组，找到最大和。|1505180|设Tm为最大值。|1505181|计算从Sm开始的精确序列，并将所有元素加到和等于Tm为止|1505182|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|S|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|T|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|U|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|V|8|@]|9|@]|A|$]]|$1|N|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|O|$]]

You are basically calculating the sum again and again.You can avoid that by storing the sums in an array.
You can do it in O(n).

Let S[0,1..n-1] be the sequence
Let T[0,1,...n-1] be the array in which T[i] is the maximum continuous sum possible starting from ith element.

Now to fill T[i], start from reverse. T[n-1]=max(S[n-1],0) 
Now T[i]=max(T[i+1]+S[i] , S[i] ,0)

Now go through the 'T' array to find the maximum sum.

Let T[m] be the max value.

To calculate the exact sequence start from S[m] and add all the elements till the sum equals T[m]

<img src="https://i.stack.imgur.com/fFz2b.jpg" alt="The Question:">

So, I have to find the maximum Sum of the continuous subset, I followed this algorithm in python.

<pre><code>def SubSeq(list):
 final_list = None
 suming = 0
 for start in range(len(list)):
 for end in range(start+1, len(list)+1):
 subseq = list[start:end]
 summation= sum(list[start:end])
 if summation &gt; suming:
 suming = summation
 final_list = subseq
 return final_list


print SubSeq([5, 15, -30, 10, -5, 40, 10])
</code></pre>

I wonder if it is a correct way in dynamic programming though the running time is <code>O(n^2)</code>. Plus, is there a possible way to make it <code>O(n)</code>

List Subsequents Method

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

​​所以，我必须找到连续子集的最大和，我在python中遵循这个算法。def SubSeq(list):    final_list = None    suming = 0    for start in range(len(list)):        for end in range(start+1, len(l...

问列表排序法
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问列表排序法EN