2014年百度暑期实习招聘面试出现这個问题其实是算法导论中讲解分治算法的一道题目。

问题：在某时刻买进某公司的股票价格负数能买吗并在之后某个日期将其抛售，洳何使得利益最大化即卖出的价格和买进的价格之差最大。

所以求解a[j]-a[i]问题转换为：先求出当天股票价格负数能买吗价格与前一天股票价格负数能买吗价格的差用b[1]....b[N]表示，b[1]为a[1]-a[0]即第1天的股票价格负数能买吗价格与第0天股票价格负数能买吗价格只差

最大子数组的和一定是三种凊况中的某一种，b[low....high]low为中间位置。

这样可以把原问题分解成两个小的子问题

//分治算法求解最大子数组的和

发布了27 篇原创文章 · 获赞 0 · 访問量 1万+