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)
#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)
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()
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)
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)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
{
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;
}