我要招人

去企业版

首页 > 试题广场 >

给定一个整数的数组，相邻的数不能同时选，求从该数组选取若干整

[问答题]

给定一个整数的数组，相邻的数不能同时选，求从该数组选取若干整数，使得他们的和最大，要求只能使用o(1)的空间复杂度。要求给出伪码。

推荐

Mathew Rice

int getMax(int a[],int len)
{
int max1 = a[0];//表示maxSum(n-2);
int max2 = a[0]>a[1]? a[0]:a[1]; //表示maxSum(n-1);
int max3 = 0; // n
for(int i =2; i<len; i++){
max3 = Max(a[i],Max(max1+a[i],max2));
// max3 = a[i]+max1> max2 ? a[i]+max1:max2; // 全部是负数也需要考虑的,这个没有
max1 = max2;
max2 = max3;
}
return max3;
}

int Max(int a,int b){
if(a>b)
return a;else
return b;
}

编辑于 2015-06-19 17:11:59 回复(0)

Henry

int getMax(int a[],int len)
{   
    int max1 = a[0];//表示maxSum(n-2);   
    int max2 = a[0]>a[1]? a[0]:a[1]; //表示maxSum(n-1);   
    int max3 = 0; // n  
    for(int i =2; i<len; i++){
         if(max1<0){     
              max3 = a[i] > max2 ? a[i]:max2;
         }else{ 
           max3 = a[i]+max1> max2 ? a[i]+max1:max2;    }    
         max1 = max2;  
         max2  = max3;  
    }  
    return max3; 
}

编辑于 2015-04-13 17:33:40 回复(4)

唐颢

int maxSum(vector<int> array)
{
    if (array.size() == 0)
        return 0;
    int fi = array[0], hi = 0;
    for (int i=1; i<array.size(); i++) {
        int nfi = hi + array[i];
        hi = max(hi, fi);
        fi = nfi;
    }
    return max(hi, fi);
}

f(i) 标识选择a[i]的情况下，a[0, ...i]的最大sum

h(i)标识不选择a[i]的情况下，a[0,...i]的最大的sum

于是有：

f(i)= h(i-1) + a[i]

h(i) = max(f(i-1), h(i-1))

发表于 2015-09-06 15:42:14 回复(0)

Carrod

// 由于有空间复杂度限制，就不能用HashMap一个个存了，空间复杂度O(n)
// 整体思路是这样的，用递归，分两种情况：
1，最后一位取了，-2后的数组情况等于原始情况，递归调用，算出sum为a+lastValue;
2，最后一位不取，-1后的数组情况等于原始情况，递归调用，算出sum为b;
终止条件是，剩下1个的话，大于0则直接返回该值，小于0直接返回0
最后比较a+lastValue和b的大小。
空间复杂度O(1)

发表于 2017-02-26 00:46:29 回复(0)

超哥哥

#include<stdio.h>

int Max3(int a,int b,int c)

{

if(a>=b&&a>=c)

return a;

else if(b>=a&&b>=c)

return b;

else

return c;

}

int anser(int A[],int n)

{

int max1,max2;

int tmp,i;

max1=A[0];

max2=A[1]>A[0]?A[1]:A[0];

for(i=2;i<n;i++)

{

tmp=max2;

max2=Max3(max2,max1,max1+A[i]);

max1=tmp;

}

return max2;

}

int main()

{

int A[]={1,2,3,-1,-3,4,-4,5,2,-1,3};

int n=11;

printf("%d\n",anser(A,n));

return 0;

}

发表于 2015-09-30 20:46:37 回复(0)

殿

<div>  int a=0;int b=0; </div> <div>          for (int i=0; i<nums.size(); i++) </div> <div>     { </div> <div>         if (i%2==0) </div> <div>         { </div> <div>             a = max(a+nums[i], b); </div> <div>         } </div> <div>         else </div> <div>         { </div> <div>             b = max(a, b+nums[i]); </div> <div>         } </div> <div>     } </div> <div>     return max(a,b); </div>

发表于 2015-09-16 16:13:34 回复(0)

商郡马


	#include <iostream>



	#include <vector>



	#include <string>



	#include <algorithm>



	#include <map>



	using namespace std;



	



	struct record{



	    int number;



	    int index;



	    int valid;



	};



	



	int cmp(const record &a, const record &b)



	{



	    return a.number < b.number;



	}



	



	int main(void)



	{



	    vector<record> input;



	    int number, idx = 0;



	



	    while(cin >> number){



	        record rec = {number, idx++, 1};



	        input.push_back(rec);



	    }



	



	    sort(input.begin(), input.end(), cmp);



	    vector<int>::size_type sz = input.size();



	



	    map<int, int> mask;



	    for(vector<int>::size_type i = 0; i < sz; ++i)



	        mask.insert(make_pair(input[i].index, i));



	



	    vector<int>::size_type i = sz - 1;



	    int sum = 0;



	



	    if(input[i].number <= 0)



	        sum = input[i].number;



	    else{



	        while(i >= 0 && input[i].number > 0){



	            vector<int>::size_type idx1, idx2;



	



	            if(!input[i].valid){



	                i--;



	                continue;



	            }



	



	            sum += input[i].number;



	            idx1 = input[i].index - 1;



	            idx2 = input[i].index + 1;



	



	            if(idx1 >= 0)



	                input[mask[idx1]].valid = 0;



	            if(idx2 < sz)



	                input[mask[idx2]].valid = 0;



	            i--;



	        }



	    }



	



	    cout << sum << endl;



	



	    return 0;



	}



	



	算法渣。排序+剔除

发表于 2015-09-10 21:48:47 回复(0)

zatrix

如果数组内所有数都大于0，那么这个问题很简单。

如果数组内的数存在≤0情况。显然选这个数是没有任何意义的。

所以对于一般情况可以进行如下计算：

def getSum(n):

for i in range(len(n)):

if n[i] <= 0:

continue

else:

sum += n[i]

i += 1

return sum

发表于 2015-06-03 14:44:44 回复(0)

wong2

aaa

发表于 2015-03-19 16:06:38 回复(0)

郎健

补充说明：

//若len为基数，取数组中

if(len>>2&1==1){

for(int i=len;i>len-k&&i>0;i=i-2;)

{

max += a[i];

}

}else{//若len偶数

for(int j=len;j>len-k&&k>0;j=j-2;)

{

max += a[i];

}

return max;

发表于 2015-02-03 18:58:35 回复(1)

asdf

int[] array
list<Integer> result
scala(){
    int count = 0
    int sum1 = 0
    int sum2 = 0
    while(count < array.size()){
        sum1 += array[count + 1]
        sum1 = sum2 + array[count + 1]
        sum2 += array[count + 2]
        sum2 = sum1 + array[count + 2]
    }
    result.add(sum1).add(sum2)
    return result;
}
result = scala(scala);
result.getMax()

发表于 2015-01-12 13:04:43 回复(4)

lenovo

发表于 2014-12-24 22:14:41 回复(0)

居AN思危

improt
int a=1

发表于 2014-12-21 19:45:02 回复(0)

大脸

发表于 2014-12-21 14:47:10 回复(0)

远方方

data = [(i, d) for i, d in emnarate(data)]

data = sorted(data, key=lambda x:x[1])

def get_max_data(data, indexes):

if not data:

return

if not indexes or data[-1][0] not in indexes:

d = data[-1]

print d

indexes.append(d[0]+1)

if d[0] != 0:

indexes.append(d[0]-1)

return get_max_data(data[:-1], indexes )

发表于 2014-12-21 07:28:42 回复(0)

Lammmmm

使用贪心法,
select(n) = no_select(n-1) + n
no_select(n) = max_sum(n – 1)
max(n) = max(select(n), no_select(n))

发表于 2014-12-17 23:02:37 回复(4)

提交观点

问题信息

贪心 2015 百度大数据开发工程师

来自：百度2015大数据云计...

上传者：小小

难度：

16条回答 141收藏 23525浏览

给定一个整数的数组，相邻的数不能同时选，求从该数组选取若干整

问题信息

热门推荐

相关试题