首页 > 代码库 > 几道动态规划

几道动态规划

1. 给一个浮点数序列,取最大乘积连续子串的值,例如 -2.5,4,0,3,0.5,8,-1,则取出的最大乘积连续子串为3,0.5,8。

 

2. 给定一个长度为N的整数数组,只允许用乘法,不能用除法,计算任意(N-1)个数的组合中乘积最大的一组,并写出算法的时间复杂度。 

 

3. 给定一个数组a[N],我们希望构造数组b[N],其中b[i]=a[0]*a[1]*...*a[N-1]/a[i]。 在构造过程:不允许使用除法; 要求:O(1)空间复杂度和O(n)时间复杂度; 除遍历计数器与a[N] b[N]外,不可使用新的变量(包括栈临时变量、对空间和全局静态变量等); 请用程序实现并简单描述。

 

几道动态规划