本文主要是介绍最小最序列和以及最小正子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.描述：最小子序列（序列之和最小）
思路：用编程之美上的分治解法。子数组存在三种情况：
（1）左边的字数组里面arr[1...n/2]
（2）右边的子数组里面arr[n/2+1...n]
（3）要么在中间 arr[start..n/2....end];
代码：
#include<iostream>using namespace std;#define max 100int findMinSubstr(int arr[],int start,int end)
{ if(start==end)return arr[start]; int left,right; int result = max;int mid = start+((end-start)>>1); left = findMinSubstr(arr,start,mid); right = findMinSubstr(arr,mid+1,end); int i = mid - 1; int j = mid + 1; int sum = arr[mid]; int minsum = max; while(i>=start){ sum += arr[i]; if(sum<minsum)minsum = sum; i--; } sum = minsum; while(j<end){ sum += arr[j]; if(sum<minsum)minsum = sum; j++; } if(minsum<left)return minsum<right?minsum:right;else return left<right?left:right;} int main()
{int arr[]={-1,7,3,-3,6};cout<<findMinSubstr(arr,0,4)<<endl;system("pause");return 0;
}2.描述：最小正子序列（序列之和最小，同时满足和值要最小）
思路：
(1)先求出数组的前缀数组之和，例如：2,-3,-3,7,5=>前缀数组和为2,-1,-4,3,8（它们的索引0 1 2 3 4）
(2)对前缀数组进行排序得到：-4,-1,2,3,8（即是这样的：(-4,3) (1,1) (2,0) (3,3,) (8,4) )
(3)则最小值一定是在：-4,1,2,3,8（结果一定在当前项减去前面一项，同时满足索引大于前一项的索引）
代码：
#include<iostream>
#include<algorithm>using namespace std;#define max 100struct Item{int value;int rank;
};bool cmp(const Item&a,const Item& b)
{return a.value<b.value;
}int operator-(const Item&a,const Item& b)
{return a.value-b.value;
}bool operator>(const Item&a,const Item& b)
{return a.rank>b.rank;
}int findMaxPositiveSubstr(int arr[],int len)
{Item *tmp = new Item[len];int sum = 0;int i; memset(tmp,0,sizeof(Item)*len);for(int i=0;i<len;i++){sum += arr[i];tmp[i].value = sum;}for(i=0;i<len;i++)tmp[i].rank = i;sort(tmp,tmp+len,cmp);int result = tmp[0].value>0?tmp[0].value:max;for(i=1;i<len;i++){if(tmp[i]>tmp[i-1]&&(tmp[i]-tmp[i-1])>0&&(tmp[i]-tmp[i-1])<result){result = tmp[i]-tmp[i-1];}}return result;
}int main()
{int arr[]={2,-3,-3,7,5};cout<<findMaxPositiveSubstr(arr,4)<<endl;system("pause");return 0;
}
3.描述：最大子序列乘积
代码：
#include<iostream> using namespace std; #define max 0;
#define min -1;long int findMaxSubstr(int arr[],int start,int end)
{ if(start==end)return arr[start]; long int left,right; int mid = start+((end-start)>>1); left = findMaxSubstr(arr,start,mid); right = findMaxSubstr(arr,mid+1,end); int i = mid - 1; int j = mid + 1; long int muilt = arr[mid]; long int minNegativeLeft = min; long int minNegativeRight = min;long int maxPostiveLeft = max;long int maxPostiveRight = max;while(i>=start){ muilt *= arr[i]; if(muilt>0){if(muilt>maxPostiveLeft)maxPostiveLeft = muilt;}else{if(muilt<minNegativeLeft)minNegativeLeft = muilt;} i--; } muilt = 1;while(j<end){ muilt *= arr[j]; if(muilt>0){if(muilt>maxPostiveRight)maxPostiveRight = muilt;}else{if(muilt<minNegativeRight)minNegativeRight = muilt;} j++; } long int tmp = minNegativeLeft*minNegativeRight>maxPostiveLeft*maxPostiveRight?minNegativeLeft*minNegativeRight:maxPostiveLeft*minNegativeRight;if(tmp>left)return tmp>right?tmp:right; else return left>right?left:right; } int main()
{ int arr[]={-1,7,3,-3,-6}; cout<<findMaxSubstr(arr,0,5)<<endl; system("pause"); return 0;
}
这篇关于最小最序列和以及最小正子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
