口试算法题

面试算法题
一个数组比如 1,2,3,-2,7；把其中任意两个相邻的数合并相加继续作为数组中的一个数，比如把2,3相加那么数组变为1,5,-2,7,问如果选择和并顺序使得结果最大,显然n个元素的数据通过n-1次合并可以得到最后的结果。最好有程序，

第一个正确答案得满分。
[最优解释]

//
//  main.cpp
//  acm
//
//  Created by BossJue  on 12-11-30.
//  Copyright (c) 2012年 __MyCompanyName__. All rights reserved.
//

#include <iostream>
using std::endl;
using std::cout;
using std::cin;

int    Search(int* array, unsigned uLen);

int main(int argc, const char * argv[])
{

    // insert code here...
    int array[]= {1,2,3,-1};
    cout<<Search(array, 4)<<endl;
    return 0;
}

int    Search(int* array, unsigned uLen){
    int**   lpDpArray;
    lpDpArray       =   new int*[uLen];
    for (int iIndex= 0; iIndex< uLen; ++iIndex) {
        lpDpArray[iIndex]           =   new int[uLen];
        lpDpArray[iIndex][iIndex]   =   array[iIndex];
    }
    for(int iDistance= 1; iDistance< uLen; ++iDistance){
        for(int iBegin= 0; iBegin+ iDistance< uLen; ++iBegin){
            lpDpArray[iBegin][iBegin+ iDistance]    =   lpDpArray[iBegin][iBegin]+ lpDpArray[iBegin+1][iBegin+ iDistance];
            for(int iPartion= iBegin+ 1; iPartion< iBegin+ iDistance; ++iPartion){
                if(lpDpArray[iBegin][iBegin+ iDistance]< lpDpArray[iBegin][iPartion]+lpDpArray[iPartion+1][iBegin+ iDistance]){
                    lpDpArray[iBegin][iBegin+ iDistance]= lpDpArray[iBegin][iPartion]+lpDpArray[iPartion+1][iBegin+ iDistance];
                }
            }
        }
    }
    int iMax=   lpDpArray[0][uLen-1];
    for(int iIndex= 0; iIndex< uLen; ++iIndex){
        delete[]    lpDpArray[iIndex];
    }
    delete [] lpDpArray;
    return iMax;
}

[其他解释]
http://blog.sina.com.cn/s/blog_631e01bf0100mal2.html
[其他解释]
没看明白啊？ 构造哈夫曼树？
两两合并 怎么选择最后结果都一样吧？
------其他解决方案--------------------

题目漏了一项就是你每次合并的时候会得到合并的分数，问最后合成一个数后得到最大的分数
[其他解释]
已有答案，不过愿共讨论！先给答案的还是给分
[其他解释]
你题目根本没说明白，不过看起来就是个简单的dp问题，没什么意思。。。
[其他解释]
很经典的问题，合并石子。f[i,j]为i~j合并的最大值，f[i,j]=max(f[i,k]+f[k,j]);大概就是这么一个公式了
[其他解释]
没看懂，不管过程怎样，最后结果不都是全部数据和么？1,2,3,-2,7四次合并之后结果必然是11，怎么和有啥区别？

[其他解释]
“每次合并的时候会得到合并的分数”
你没说合并的分数是什么东西或者它是怎么得出来的？
[其他解释]
不懂。。。表达不清
[其他解释]
无论怎么合并和都不变

引用:

没看懂，不管过程怎样，最后结果不都是全部数据和么？1,2,3,-2,7四次合并之后结果必然是11，怎么和有啥区别？

[其他解释]
你的意思是求最大子序列和吗？
[其他解释]
//这样可以吗？
#include<iostream.h>
#define N 5
int main()
{
int k=0,l=0,i,j,n,a[N];
for(i=0;i<N;i++)
cin>>a[i];
for(n=N-1;n>0;n--)
{
l=0;j=0;
for(i=0;i<n;i++)
{
if(a[i]+a[i+1]>l)
{
l=a[i]+a[i+1];
j=i;
}
}
k=k+l;
a[j]=a[j]+a[j+1];
for(i=j+1;i<n;i++)
{
a[i]=a[i+1];
}
}
cout<<k;
return 0;
}
[其他解释]
只能想到遍历N-2次，每次找到得分最高的合并方式。似乎时间复杂度太高
[其他解释]
S

引用:

只能想到遍历N-2次，每次找到得分最高的合并方式。似乎时间复杂度太高

那改成第一次找，接下来就肯定是它加上它的下一个数或上一个数为最大?
[其他解释]

#include <stdio.h>

void accumulate(int array[], int n){
// until中存储的是以i位置元素终止的最大值，f，t是起始和终止索引
// max mf mt记录正果序列以i位置元素终止的最大值，起始和终止索引
int max, until, f, t, mf,mt, i;
if(n < 1) return;
max = until = array[0];
mf = mt = f = t = 0;
for(i = 1; i < n; ++i){
if(until <= 0){
until = array[i];
f = t = i;
} else {
until = until + array[i];
t = i;
}

if(until > max){
max = until;
mf = f;
mt = t;
}
}
printf("max combine between %d and %d, value is %d", mf, mt, max);
}

int main(){
int array[] = {-1, -5, 8, -3, 6, -12, -2};
accumulate(array, sizeof(array)/sizeof(int));
return 0;
}

[其他解释]
不好意思，我题目是说的不够清楚，其实原题是一个石子合并的问题，有一堆石头，每个石头的分数用一个整数表示，每次把相邻的石头合并并得到这一次合并的两堆石头代表的分数，直到合并为一堆石头。还有这的确是一个很水的dp，可怜我是个菜鸟，不过已给出的答案没有正确的,5楼的dp也不太正确，或者不完整。
[其他解释]

你以为20分很高？还全给？表述这么多次没一次清楚的，面试题你直接扫描啊！
[其他解释]
我没说高啊，说全给也没说错吧，既然是水题，分也不高，dp的给个状态转移方程总行吧！不要在那吐槽了。
[其他解释]


顶楼上。。。
[其他解释]

貌似值都用一样
[其他解释]
你等着，我回去给你写代码，我要分
[其他解释]
。。。还是没明白题
[其他解释]
怎么觉得按照题目，顺序没关系，也不会有最大结果呢，加法的交换律吗，怎么加都一样啊？
[其他解释]
非常感谢各位的回复！
[其他解释]
的确是19楼说的那道题，23楼基本上是正确答案了！
不过lpDpArray[iBegin][iBegin+ iDistance]= lpDpArray[iBegin][iPartion]+lpDpArray[iPartion+1][iBegin+ iDistance];这一句在分号前要加上sum(iBegin->iBegin+ iDistance)，详见19楼链接。
结贴给分。
[其他解释]
不知道你说的什么
[其他解释]
可千万不要直接写程序，就算算出来也肯定不行。先用脑子想想，其实那是在替客户着想，这是题的意思。

好了，话不多说，赶快结贴，第一次回答问题，给分吧
[其他解释]
一个规划算法 呵呵
[其他解释]
问下楼主，贪心行不？每次合并的是当前最大的两个数，直到合并完成。
[其他解释]
优先级队列，也行吧
[其他解释]
这是一个动态规划的问题！
[其他解释]
null
[其他解释]
算法什么的对我来说，还是太难了！
[其他解释]

引用:

这是一个动态规划的问题！

  贪心也行吧 = =

查看更多 下一篇