问题
给定一个长度为N的数组，找出最长的单调自增子序列(不一定连续，但顺序不能乱)。例如，给定一个长度为6的数组A{5， 6， 7， 1， 2， 8}其最长单调递增子序列为{5、6、7、8}，长度为4.
最长递增子序列
O(NlgN）算法
假设有一个序列d[1..9] ={ 2，1 ，5 ，3 ，6，4， 8 ，9， 7}，可见其LIS长度为5。 一步一步地试着找出它。 我们定义一个序列B，然后命令 i = 1 to 9 对此序列进行逐一调查。 另外，我们用一个变量Len来记录现在最长计算了多少
首先，将d[1]有序地放入b中，使b[1] = 2.也就是说，当只有一个数字2时，长度为1的LIS的最小末尾是2。此时Len=1
然后，将d[2]有序地放入b中，使b[1] = 1.也就是说，长度为1的LIS的最小末尾是1，d[1]=2已经没用了，很容易理解。此时Len=11
接着，d[3] = 5，d[3]>B[1]因此，让B[1+1]=B[2]=d[3]=5，也就是说，长度为2的LIS的最小末尾是5，这很容易理解。此时，B[1..2] = 1, 5，Len＝2
再来，d[4] = 3.它只是加在1和5之间，显然不适合放在1的位置，因为1小于3，长度为1的LIS最小末端应该是1，所以很容易推断长度为2的LIS最小末端是3，所以5可以淘汰。此时，B[1..2] = 1, 3，Len = 2
继续，d[5] = 6.它在3后面，因为B[2] = 3, 而6在3后面，所以很容易推断B[3] = 6, 这时B[1..3] = 1, 3, 6.还是容易理解吧？ Len = 3 了噢。
第6个, d[6] = 4.你可以看到它在3和6之间，所以我们可以替换6，得到B[3] = 4。B[1..3] = 1, 3, 4， Len继续等于3
第7个, d[7] = 8.它很大，比4大，嗯。所以B[4] = 8.Len变成了4
第8个, d[8] = 9.获得B[5] = 9.嗯。Len继续增加，到5。
最后一个, d[9] = 7.它在B[3] = 4和B[4] = 在8之间，所以我们知道最新的B[4] =7，B[1..5] = 1, 3, 4, 7, 9，Len = 5。
所以我们知道LIS的长度是5。
请注意，这个1、3、4、7、9不是LIS，而是存储相应长度LIS的最小末端。有了这个结局，我们可以一个接一个地插入数据。尽管最后一个d[9] = 7更新对这组数据没有意义，但如果两个数字出现在后面 8 和 9，然后可以将8更新到d[5]， 9更新到d[6]，得出LIS长度为6。
然后我们应该找到一件事：在B中插入数据是有序的，并且在不移动的情况下进行替换——也就是说，我们可以使用两点搜索将每个数字的插入时间优化到O(logN)因此，算法的时间复杂度降低到O(NlogN)～！ 代码如下(代码中的数组B从位置0开始存储数据)
#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 9 ///数组元素数 int array[N] = {2, 1, 6, 3, 5, 4, 8, 7, 9}; //原数组 int B[N]; //动态规划中使用的数组用于记录中间结果，其含义三言两语。请参阅博客的解释 int len; ////用于标记B数组中的元素个数 int LIS(int *array, int n); 计算最长递增子序列的长度，计算B数组的元素，array[]循环完成后，B的长度len为所需 int BiSearch(int *b, int len, int w); ////修改后的二分搜索算法 int main() { printf("LIS: %d\n", LIS(array, N)); int i; for(i=0; i<len; ++i) { printf("B[%d]=%d\n", i, B[i]); } return 0; } int LIS(int *array, int n) { len = 1; B[0] = array[0]; int i, pos = 0; for(i=1; i<n; ++i) { if(array[i] > B[len-1]) //如果大于B中最大元素，直接插入B数组末尾 { B[len] = array[i]; ++len; } else { pos = BiSearch(B, len, array[i]); ///二分搜索需要插入的位置 B[pos] = array[i]; } } return len; } //修改后的二分搜索算法，返回需要插入数组元素的位置。 int BiSearch(int *b, int len, int w) { int left = 0, right = len - 1; int mid; while (left <= right) { mid = left + (right-left)/2; if (b[mid] > w) right = mid - 1; else if (b[mid] < w) left = mid + 1; else ///找到了这个元素，则直接返回 return mid; } return left;///如果该元素不存在于数组B中，则返回该元素应插入的位置 }问题 对于形如：int arr[] = { 1, -5, 3, 8, -9, 6 };数组，找出其最大连续子序列和。 若数组中的所有元素都是正数，则最大连续子序列和整个数组。 若数组中所有元素均为负数，则最大连续子序列和空序列，最大和为0。
class Solution {public: int FindGreatestSumOfSubArray(vector<int> array) { if(array.size()==0) return 0; int dp[array.size()]; dp[0]=array[0]; int result=array[0]; for(int i=1;i<array.size();i++) { dp[i]=max(array[i],dp[i-1]+array[i]); result=max(result,dp[i]); } return result; }};考虑到乘积子序列中有正有负或0，我们可以将问题简化为：在数组中找到子序列，使其乘积最大；同时找到子序列，使其乘积最小（负）。因为虽然我们只需要一个最大的积累，但由于负的存在，我们很容易同时找到这两个乘积。换句话说，它不仅记录了最大乘积，而且还记录了最小乘积。
假设数组是a[]，直接使用动态规划来解决，考虑到负数的可能性，我们用maxend来表示a[][i]用minend表示结尾最大连续子串的乘积值[i]最小子串的乘积值为：
maxend = max(max(maxend * a[i], minend * a[i]), a[i]); minend = min(min(maxend * a[i], minend * a[i]), a[i]);首先考虑不连续的
思路：一维动态规划
考虑到乘积子序列中有正有负或0，问题可以简化为这样：
在数组中找到子序列，使其乘积最大；同时找到子序列，使其乘积最小(负数)。 虽然只有一个最大积，但由于负数的存在，最小乘积也应该被记录下来。当遇到新的负数元素时，乘以最小乘积后得到最大值。
代码：
int maxSuccessiveProduct(int num[], int n){ if(n < 1) return INT_MIN; int max_prod = num[0], min_prod = num[0]; int max_res = max_prod; for(int i = 1; i < n; ++i) { int cur_prod1 = max_prod * num[i]; int cur_prod2 = min_prod * num[i]; max_prod = max(max_prod, max(cur_prod1， cur_prod2); min_prod = min(min_prod, min(cur_prod1， cur_prod2); max_res = max(max_prod, min_prod); } return max_res;}再考虑连续性
思路：
与不连续相似，但如果最大乘积是最大乘积，则应同时记录当前子串的最大/最小乘积<当前值开始新的子串。
代码：
int maxProduct(int A[], int n) { int maxEnd = A[0]; int minEnd = A[0]; int maxResult = A[0]; for (int i = 1; i < n; ++i) { int end1 = maxEnd * A[i], end2 = minEnd * A[i]; maxEnd = max(max(end1, end2), A[i]); //与上述区别在于，外max的另一个参数是当前元素值 minEnd = min(min(end1, end2), A[i]); maxResult = max(maxResult, maxEnd); } return maxResult;}
湘公网安备43019002002060