频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
微软等数据结构与算法面试100题 第三题
2012-08-21 09:24:09      个评论      
收藏   我要投稿

第三题

题目:
输入一个整型数组,数组里面有正数也有负数,数组中连续的一个或者多个数组成一个子数组,每个子数组都有一个和。
求,所有子数组的和的最大值。要求时间复杂度为O(n)

分析:
本题是一个典型的使用动态规划算法的题目。
动态规划算法的使用基本要素是1、最优子结构(当问题的最优解包含了其子问题的最优解,成该问题具有最优子结构性质)
2、重叠子问题(也就是说如果使用递归算法自顶朝下求解问题时,每次产生的子问题并不是新问题,有一些子问题被反复计算多次)。
对于本题,要求计算和最大的一个子数组,对于是不是最优子结构的分析,假设数组为a[] (size=n),那么可以分割成为0-n-2和1-n-1两个子问题。
这两个子问题里面又都包含1-n-2子问题,可以使用递归算法,但是由于使用递归算法会造成大量的子问题的求解,因此使用动态规划算法。

动态规划算法
设SUM[i]为前i个元素中,包含第i个元素且和最大的连续数组,result为已找到的子数组中最大的,对于第i+1个元素,有两种选择,1.作为新子数组的
第一个元素,2.放入前面找到的数组。

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

本题若使用顺序求解算法 复杂度为O(n^2),递归求解算法复杂度为O(nlogn),动态规划算法复杂度为O(n)
顺序求解

递归求解

动态规划

代码:

[cpp] 
#include<iostream> 
 
using namespace std; 
 
int maxSubArray(int *a, const int length) 

    int maxSumSubArray = 0; 
 
    int sum_i = 0; 
 
    for(int i=0; i <length; i++) 
    { 
        sum_i = sum_i + a[i]; 
 
        if(sum_i < 0) sum_i = 0; 
        else 
        { 
            if(sum_i > maxSumSubArray) maxSumSubArray = sum_i; 
        } 
     
    } 
 
    //若是数组中的元素均为负值 
    if(sum_i==0) 
    { 
        for(int i=0; i < length; i++) 
        { 
            if(a[i] > maxSumSubArray) maxSumSubArray = a[i]; 
        } 
    } 
     
    return maxSumSubArray; 
     

 
int main() 

 
    int a[10] = {1, 3, -3, -4 ,5 ,-2, 6, -1, 2, -6}; 
    int length = sizeof(a)/sizeof(int); 
 
    cout<<maxSubArray(a,length); 
    return 0; 
 
 

 

点击复制链接 与好友分享!回本站首页
上一篇:微软等数据结构与算法面试100题 第二题
下一篇:微软等数据结构与算法面试100题 第四题
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站