求子数组问题

本文主要是介绍求子数组问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

子数组问题分为三类：

1：连续子数组

2：非连续子数组

3：可连续也可以不连续

这三类问题的解决办法一般都是循环或者动态规划，尝试了dfs算法，结果把自己给绕进去了！

一：最大升序问题（属于第三类）

参考：https://www.cnblogs.com/lerongwei/p/4890633.html

1：动态规划解法：

利用动态规划来做，假设数组为1, -1, 2, -3, 4, -5, 6, -7。我们定义LIS[N]数组，其中LIS[i]用来表示以array[i]为最后一个元素的最长递增子序列。
使用i来表示当前遍历的位置：
当i = 0 时，显然，最长的递增序列为（1），则序列长度为1。则LIS[0] = 1
当i = 1 时，由于-1 < 1，因此，必须丢弃第一个值，然后重新建立序列。当前的递增子序列为（-1），长度为1。则LIS[1] = 1
当i = 2 时，由于2 > 1，2 > -1。因此，最长的递增子序列为(1, 2)，(-1, 2)，长度为2。则LIS[2] = 2。
当i = 3 时，由于-3 < 1, -1, 2。因此，必须丢掉前面的元素，重建建立序列。当前的递增子序列为（-3），长度为1。则LIS[3] = 1。
依次类推之后，可以得出如下结论。
LIS[i] = max{1, LIS[k] + 1}, array[i] >array[k], for any k < i
最后，我们取max{Lis[i]}。

#include<stdio.h>
#include<iostream>
using namespace std;
void FindLongestAscSequence( int *input,int size){
int *list = new int[size];// 用来存储以第i个元素结尾的最长递增子序列
int *sum = new int[size]; // 用来存储以第i个元素结尾的最长递增子序列的和
int MaxLen = 1;
int maxsum =0;
int k = 0;
for (int i = 0; i < size; i++){
list[i] = 1 ;
sum[i] = input[i]; //初始为
for ( int j = 0; j < i; j++){
if ((input[i] > input[j]) && (list[j] + 1 > list[i]) )
list[i] = list[j] + 1;
if ((input[i] > input[j]) && (sum[j] + input[i] > sum[i]) )
sum[i] = sum[j] + input[i];

}
if (MaxLen < list[i]){
MaxLen = list[i];
}
if (maxsum < sum[i])
{
maxsum = sum[i];
}
}
cout<<MaxLen << ' '<< maxsum << endl;
}

int main(){
int test1[] = {5,1,3,4,9,7,6,8};
int test2[] = {1,2,3,4,5,6};
int test3[] = {6,5,4,3,2,1};
FindLongestAscSequence(test1,8);
FindLongestAscSequence(test2,6);
FindLongestAscSequence(test3,6);
return 0;
}

这个通用解法可以实现求最大子数组的长度和求和问题。网上还有一种循环的解法但是没有回溯，得到的结果并不是我我们想要的额！

#include<stdio.h>
#include<iostream>
using namespace std;
void FindGreatestAddOfSubArrey(int *input,int size){
int *result = new int[size];
int *pre = new int[size];
int k,MaxLen = 0;
for (int len = 0; len < size; len++){
int temp = input[len];
int cnt = 0;
pre[0] = input[len];
for(int end = len + 1; end < size; end++){
if (input[end] > temp){
temp = input[end];
pre[++cnt] = temp;
}
}
if (cnt >= MaxLen){
k = 0;
MaxLen = cnt;
while(k <= cnt){
result[k] = pre[k];
k++;
}
}
}
cout<<MaxLen+1<<endl;
for(int i = 0;i < k; i++)
cout<<result[i]<<" ";
cout<<endl;
}

int main(){
int test1[] = {5,1,3,4,9,7,6,8};
int test2[] = {1,2,3,4,5,6};
int test3[] = {6,5,4,3,2,1};
FindGreatestAddOfSubArrey(test1,8);
FindGreatestAddOfSubArrey(test2,6);
FindGreatestAddOfSubArrey(test3,6);
return 0;
}

二：数组非连续子序列的最大和

动态规划：找递推关系式！

从《编程之美》一题中得到启发，我们是不是也可以用动态规划的方法来解这道题呢？假设从原数组a第i位开始的最大不连续子数组和为m[ i ]，那么它的值有两种可能，一种是当前元素a[ i ]与隔一位上子问题解m[ i+2 ]之和（由不连续性质决定），另一种是不包含当前元素而直接等于前一位上子问题解m[ i+1 ]，那么我们可以写出递推公式为：m[ i ] = max(a[ i ] + m[ i+2 ], m[ i+1 ])。
等等，也许你要说，好像这个递推式有漏洞啊，因为前一位上的解m[ i+1 ]本身就有可能是包含或不包含a[ i+1 ]，假如m[ i+1 ]不包含a[ i+1 ]，那么岂不是还要考虑a[ i ]+m[ i+1 ]这种可能性呢？
这个递推式真的经不起推敲吗？我们不妨重新整理一下思路：由于原数组上每一元素都有取与不取两种可能，那么也就对应有包含和不包含该元素的两个子数组的最大和。对于原数组a中第i位上的元素，假设包含a[ i ]元素的子数组最大和为s[ i ]，而不包含元素a[ i ]的子数组最大和为ns[ i ]，因此所要求的不连续子数组最大和m[ i ] = max(s[ i ], ns[ i ])。那么根据题意我们可以整理出递推关系如下：
s[ i ] = max(a[ i ] + ns[ i+1 ], a[ i ] + m[ i+2 ])
ns[ i ] = m[ i+1 ]
m[ i ] = max(a[ i ] + ns[ i+1 ], a[ i ] + m[ i+2 ], m[ i+1 ])
有趣的地方在于ns[ i ] = m[ i+1 ]这一项上，根据它我们可以得到ns[ i+1 ] = m(i+2)，也就是说假如m[ i+1 ]不包含a[ i+1 ]的话，那么它一定等于m[ i+2 ]，所以a[ i ]+ns[ i+1 ]等价于a[ i ] + m[ i+2 ]，递推式m[ i ] = max(a[ i ] + m[ i+2 ], m[ i+1 ])是正确的！
从《编程之美》给出的解法中得到启发，我们也只需要使用两个变量来记录m[ i+2 ]和m[ i+1 ]的值就行了，而且同样只需要O(N)的复杂度就可以解这道题，代码如下：

#include<stdio.h>
#include<iostream>
using namespace std;
static int max(int a,int b)
{
return a > b? a: b;
}

int maxSubSum(int a[] , const int len)
{

a[1] = max(a[1],a[0]);

for (int i = 2; i < len; i++) {

a[i]= max( max(a[i],a[i-1]),a[i-2]+a[i]);

}
return a[len-1];
}

//编程之美的解法
int maxsum(int* a, int n)
{
int m2 = 0;
int m1 = a[ n-1 ];
for(int i = n - 2; i >= 0; i--)
{
if(m2 < 0) m2 = 0; //处理最后一位为负数或全为负数的情况
int tmp = m1;
m1 = max(a[ i ] + m2, m1);
m2 = tmp;
}
return m1;
}


int main( )
{