快速寻找满足条件的两个数
解法1
hashmap存数据,先遍历数组,查找hashmap中是否存在给定和-a[i]的值,时间复杂度O(n)
解法2
1.排序,2. 设定收尾指针,a[start]+a[end] < num,则star++,>,则end–,=,则return
子数组的最大乘积
给定一个长度为N的整数数组,只允许用乘法,不能用除法,计算任意(N-1)个数的组合中乘积最大的一组,并写出算法的时间复杂度
解法
s[i-1] i t[i+1]
如上图,array[]为初始数组
s[i]表示前i个元素的乘积,1<=i<=N,s[0] = 1,s[i] = s[i-1]*array[i-1]
t[i]表示数组后(N-i)个元素的乘积,1<=i<=N,t[N+1]=1,
t[i] = t[i+1]*array[i]
p[] = s[i-1]*t[i+1]
方法:先分别从头到尾和从尾到头扫描数组两次,可得到s[]和t[],在遍历一次数组即可得到p[],时间复杂度为O(N)
求数组的子数组之和的最大值
所给数组A[0]…A[n-1]
解法1
动态规划思路:分治(大问题转换为小问题) + 元素和除该元素结果的关系
可以考虑数组的第一个元素A[0],以及最大的一段数组(A[i],…,A[j])和A[0]的关系:
- 当 0=i=j时,元素A[0]本身构成和最大的一段
- 当 0=i<j时,子数组之和由A[0]开始
- 当 0<i时,元素A[0]和子数组之和没有关系
即 All[0]=max{A[0],A[0]+start[1],All[1]}
,其中,start[1]表示子数组之和包含A[0],从A[1]开始的最大子数组之和,All[1]表示A[1]…A[j]的最大子数组之和。从尾开始遍历
int max(int[] A){
int[] start = new int[A.length()];
int[] All = new int[A.length()];
for(int i = n-2; i >=0 ; i--){
all[i] = Math.max(A[i],Math.max(A[i]+start[i+1],all[i+1]));
}
return all[0];
}
解法2
public int FindGreatestSumOfSubArray(int[] array) {
int max = Integer.MIN_VALUE;
int res = 0;
for(int i = 0; i < array.length; i++){
if(res >= 0){
res = res + array[i];
}else{
res = array[i];
}
if(res > max){
max = res;
}
}
return max;
}
若A[n-1]和A[0]收尾相邻,找和最大,把题目分为两种情况
- 解没有跨过A[n-1]到A[0](原问题)
- 解跨过A[n-1]到A[0]
对于第二种情况,只要找到从A[0]开始和最大的一段0…j(0 <= j < n),以及以A[n-1]结尾的和最大的一段i…n-1(0 <= i < n),和最大值M_2
M_2 = A[i]+...+A[n-1]+A[0]+...+A[j]
如果 i<=j
M_2 = A[0]+...+A[n-1]
否则
M_2 = A[0]+...+A[j]+A[i]+...+A[n-1]
求数组的子数组之和的最大值(二维)
二维数组求解最大值
解法1
首先计算区域和,然后排序比较,ps[i][j]表示区域0-i,0-j的所有元素之和
for(int i = 0; i <= n; i++)
ps[i][0] = 0;
for(int j = 0; j <= m; j++)
ps[0][j] = 0;
for(int i=1; i <= n; i++)
for(int j = 1; j <= m; j++)
ps[i][j] = ps[i-1][j] + ps[i][j-1]-ps[i-1][j-1] + B[i][j]
时间复杂度O(N^2*M^2)
解法2
二维转一维
int MaxSum(int[] A, int n, int m){
maximun = Integer.MIN_VALUE;
for(int a = 0; a < n; a++){
for(int c = a; c < n; c++){
start = BC(a,c,m);
All = BC(a,c,m);
//一维数组的解法
}
}
}
其中 BC(a,c,i)表示在第a行和第c行之间的第i列的所有元素之和,即总体可看成一个一维数组。
数组分割???
- 有一个无序,元素个数为2n的正整数数组,要求:如何能把这个数组分割为元素个数为n的两个数组,并使两个子数组的和最接近
解法
假设数组A[1…2n]所有元素的和是SUM,模仿动态规划解0-1背包问题,令S(k,i)表示前k个元素中任意i个元素的和的集合,即S(k.i)={S1,S2…}.
- S(k, 1) = {A[i] | 1<= i <= k}
- S(k, k) = {A[1]+A[2]+…+A[k]}
- S(k, i) = S(k-1, i) U {A[k] + x | x属于S(k-1, i-1) }
按照这个递推公式来计算,最后找出集合S(2N, N)中与SUM/2最接近的那个和,这便是答案,这个算法的时间复杂度是O(2^N).
因为这个过程中只关注和不大于SUM/2的那个子数组的和。所以集合中重复的和以及大于SUM/2的和都是没有意义的,有意义的和的个数最多就是SUM/2个。所以,我们不需要记录S(2N,N)中都有哪些和,只需要从SUM/2到1遍历一次,逐个询问这个值是不是在S(2N,N)中出现,第一个出现的值就是答案。这个是网上C++版本的答案,本人实际上还不是太理解,如果有更好的解释方式,也请大牛们赐教
int arr[] = {0,1,5,7,8,9,6,3,11,20,17};
const int N=5;
const int SUM = 87;
// 模仿动态规划解0-1背包问题的策略
int solve1()
{
int i , j , s;
int dp[2*N+1][N+1][SUM/2+2];
/*
用dp(i,j,c)来表示从前i个元素中取j个、且这j个元素之和不超过c的最佳(大)方案,在这里i>=j,c<=S
状态转移方程:
限第i个物品不取
dp(i,j,c)=max{dp(i-1,j-1,c-a[i])+a[i],dp(i-1,j,c)}
dp(2N,N,SUM/2+1)就是题目的解。
*/
//初始化
memset(dp,0,sizeof(dp));
for(i = 1 ; i <= 2*N ; ++i)
{
for(j = 1 ; j <= min(i,N) ; ++j)
{
for(s = SUM/2+1 ; s >= arr[i] ; --s)
{
dp[i][j][s] = max(dp[i-1][j-1][s-arr[i]]+arr[i] , dp[i-1][j][s]);
}
}
}
//因为这为最终答案 dp[2*N][N][SUM/2+1];
i=2*N , j=N , s=SUM/2+1;
while(i > 0)
{
if(dp[i][j][s] == dp[i-1][j-1][s-arr[i]]+arr[i]) //判定这个状态是由哪个状态推导出来的
{
cout<<arr[i]<<" "; //取中arr[i]
j--;
s -= arr[i];
}
i--;
}
cout<<endl;
return dp[2*N][N][SUM/2+1];
}