动态规划（21）
给一个浮点数序列，取最大乘积子序列的值，例如
-2.5，4，0，3，0.5，8，-1，则取出的最大乘积子序列为3，0.5，8。
解法一：用动态规划来做。
& & 假设数组为a[]，直接利用动归来求解，考虑到可能存在负数的情况，我们用Max[i]来表示以a[i]结尾的最大连续子序列的乘积值，用Min[i]表示以a[i]结尾的最小的连续子序列的乘积值，那么状态转移方程为：
& & & &Max[i]=max{a[i], Max[i-1]*a[i], Min[i-1]*a[i]};
& & & &Min[i]=min{a[i], Max[i-1]*a[i], Min[i-1]*a[i]};
&& &初始状态为Max[1]=Min[1]=a[1]。代码如下：
给定一个整数数组，有正有负数，0，正数组成,数组下标从1算起
求最大连续子序列乘积，并输出这个序列，如果最大子序列乘积为负数，那么就输出-1
用Max[i]表示以a[i]结尾乘积最大的连续子序列
用Min[i]表示以a[i]结尾乘积最小的连续子序列
因为有复数，所以保存这个是必须的
void longest_multiple(int *a,int n){
int *Min=new int[n+1]();
int *Max=new int[n+1]();
int *p=new int[n+1]();
for(int i=0;i&=n;i++){
Min[1]=a[1];
Max[1]=a[1];
int max_val=Max[1];
for(int i=2;i&=n;i++){
Max[i]=max(Max[i-1]*a[i],Min[i-1]*a[i],a[i]);
Min[i]=min(Max[i-1]*a[i],Min[i-1]*a[i],a[i]);
if(max_val&Max[i])
max_val=Max[i];
if(max_val&0)
printf(&%d&,-1);
printf(&%d&,max_val);
//内存释放
delete [] M
delete [] M
数组中找一个子序列，使得它的乘积最大；同时找一个子序列，使得它的乘积最小（负数的情况）。因为虽然我们只要一个最大积，但由于负数的存在，我们同时找这两个乘积做起来反而方便。也就是说，不但记录最大乘积，也要记录最小乘积。所以，我们让maxCurrent表示当前最大乘积的candidate，minCurrent表示当前最小乘积的candidate，（用candidate这个词是因为只是可能成为新一轮的最大/最小乘积），而maxProduct则记录到目前为止所有最大乘积candidates的最大值。
& & 由于空集的乘积定义为1，在搜索数组前，maxCurrent,minCurrent,maxProduct都赋为1。
假设在任何时刻你已经有了maxCurrent和minCurrent这两个最大/最小乘积的candidates，新读入数组的元素x(i)后，新的最大乘积candidate只可能是maxCurrent或者minCurrent与x(i)的乘积中的较大者，如果x(i)&0导致maxCurrent&minCurrent，需要交换这两个candidates的值。
& & 当任何时候maxCurrent&1，由于1（空集）是比maxCurrent更好的candidate，所以更新maxCurrent为1，类似的可以更新minCurrent。任何时候maxCurrent如果比最好的maxProduct大，更新maxProduct。
& & 具体代码如下：
template &typename Comparable&
Comparable maxprod( const vector&Comparable&&v)
Comparable maxProduct = 1;
Comparable minProduct = 1;
Comparable maxCurrent = 1;
Comparable minCurrent = 1;
for( i=0; i& v.size() ;i++)
maxCurrent *= v[i];
minCurrent *= v[i];
if(maxCurrent & maxProduct)
maxProduct = maxC
if(minCurrent & maxProduct)
maxProduct = minC
if(maxCurrent & minProduct)
minProduct = maxC
if(minCurrent & minProduct)
minProduct = minC
if(minCurrent & maxCurrent)
swap(maxCurrent,minCurrent);
if(maxCurrent&1)
maxCurrent = 1;
//if(minCurrent&1)
minCurrent =1;
return maxP
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：523532次
积分：8321
积分：8321
排名：第2105名
原创：279篇
转载：86篇
译文：19篇
评论：33条
(12)(12)(7)(9)(61)(32)(1)(26)(1)(2)(53)(28)(2)(26)(73)(23)(4)(2)(4)(2)(4)解决?android:attr/listPreferredItemHeightSmall requires API level 14 (current min is 10)问题
Android-解决Navigation Drawer自定义drawer_list_item.xml在API14以下版本中不能添加两个attr的问题
android:minHeight=&?android:attr/listPreferredItemHeightSmall&
android:textAppearance=&?android:attr/textAppearanceListItemSmall& 如果AndroidMenifest中的android:minSdkVersion=&？&低于14的话会出现?android:attr/listPreferredItemHeightSmall requires API level 14 (current min is 10)类似的错误。
解决方法为：
在value/attrs.xml文件中自定义属性 &?xml version=&1.0& encoding=&utf-8&?&
&resources&
&declare-styleable name=&Theme&&
&!-- Attributes below are needed to support the navigation drawer on Android 3.x. --&
&!-- A smaller, sleeker list item height. --&
&attr name=&myapp_listPreferredItemHeightSmall& format=&dimension& /&
&!-- Drawable used as a background for activated items. --&
&attr name=&myapp_activatedBackgroundIndicator& format=&reference& /&
&!-- The preferred TextAppearance for the primary text of small list items. --&
&attr name=&myapp_textAppearanceListItemSmall& format=&reference& /&
&/declare-styleable&
&/resources&
修改value-v11/styles.xml &resources&
&!-- Base application theme for API 11+. This theme completely replaces --&
&!-- AppBaseTheme from res/values/styles.xml on API 11+ devices. --&
&style name=&AppBaseTheme& parent=&android:Theme.Holo&&
&!-- API 11 theme customizations can go here. --&
&!-- Implementation of attributes needed for the navigation drawer as the default implementation is based on API-14. --&
&item name=&myapp_listPreferredItemHeightSmall&&48dip&/item&
&item name=&myapp_textAppearanceListItemSmall&&@style/MyappDrawerMenu&/item&
&item name=&myapp_activatedBackgroundIndicator&&@drawable/ab_transparent_action_bar&/item&
&style name=&MyappDrawerMenu&&
&item name=&android:textSize&&16sp&/item&
&item name=&android:textStyle&&bold&/item&
&item name=&android:textColor&&?android:attr/actionMenuTextColor&/item&
&/resources&
修改value-v14 &resources&
&!-- Base application theme for API 14+. This theme completely replaces --&
&!-- AppBaseTheme from BOTH res/values/styles.xml and --&
&!-- res/values-v11/styles.xml on API 14+ devices. --&
&style name=&AppBaseTheme& parent=&android:Theme.Holo&&
&!-- For API-14 and above the default implementation of the navigation drawer menu is used. Below APU-14 a custom implementation is used. --&
&item name=&myapp_listPreferredItemHeightSmall&&?android:attr/listPreferredItemHeightSmall&/item&
&item name=&myapp_textAppearanceListItemSmall&&?android:attr/textAppearanceListItemSmall&/item&
&item name=&myapp_activatedBackgroundIndicator&&?android:attr/activatedBackgroundIndicator&/item&
&/resources&
最后就是在drawer_list_item.xml中应用自定义属性： 把&TextView中的： android:minHeight=&?android:attr/listPreferredItemHeightSmall&
android:textAppearance=&?android:attr/textAppearanceListItemSmall& 修改为：
android:minHeight=&?attr/myapp_listPreferredItemHeightSmall&
android:textAppearance=&?attr/myapp_textAppearanceListItemSmall&