算法-一个整形数组，求出满足要求的值

Question

一个整型数组，例如 4 5 2 3 1 7 9
假如数组中每个元素表示的是股票的价格，例如 第一天是4元、第二天是5元，以此类推。。。
现在问，该在哪天买入股票，哪天卖出股票，收益最大。显然上面的例子中，第五天以1元买入，第七天以9元卖出，收益最大。
需要算法时间复杂度为 O(n) 空间复杂度是O(1)

Answer 1

暂时想到这样一个办法：除最后一个数外，其它数均与其后面的最大数相减，找出绝对值最大的那一对数。

Answer 2

这是个很经典的动态规划算法
很显然要让利益最大化，每天结束后要么全仓持有股票，要么空仓持有现金。
记h[n]为第n天空仓持有现金时的最大收益，g[n]为第n天全仓持有股票时的最大股票数
则
h[n] = max( h[n-1], g[n-1] * c[n])
g[n] = max( g[n-1], h[n-1] / c[n])

其中c[n]为第n天的股价。
最后一天要卖出股票，所以只要记h[N]就是最后的答案

如果限定只能买卖一次：
h[n] = max( h[n-1], g[n-1] * c[n])
g[n] = max( g[n-1], C_0 / c[n])
C_0是初始的现金数。可以设成1。即不允许通过卖了股票之后再买进的方式赚钱，只允许一次买进。
最后答案仍然是h[n]。

以下作废，不过因为是讨论了扩展情况，就保留在这里了
如果股票数必须是整数：
把g[n]改成两个数组g1[n]和g2[n]，g1[n]表示持有的最大股票数，g2[n]表示在此条件下剩余的现金

h[n] = max( h[n-1], g1[n-1] * c[n] + g2[n] )
{g1[n], g2[n]} = max( {g1[n-1], g2[n-1]}, {h[n-1] / c[n], h[n-1] % c[n]})
//优先比较g1[n]，g1[n]相同时比较g2[n]
因为g2[n]的金额一定不足一股，因此股票数较大的总资产一定比较大；股票数相等时再比较剩余现金

Answer 3

void find_rand(int *data, int n, int &low, int &high)
{
int *ss = new int[n];
ss[0] = 0;
int f = 0;
low =0;
high = 0;
for(int i=1; i< n; ++i)
{
ss[i] = data[i] - data[f];
if(ss[i] < 0)
f = i;
}
int max = ss[0];
for(int i=1; i< n; ++i)
if(ss[i] > max)
{
max = ss[i];
high = i;
}
for (int i = high; i> 0;--i)
{
if(ss[i] <= 0)
{
low = i;
break;
}
}
delete []ss;

}
low 表示什么时候买进，high表示什么时候卖出

Answer 4

<?php

/*

复杂度 O(n)

用到四个临时变量

$min - 储存最小值，未必会成为购买值
$s = 购买值
$e = 卖出值
$L = 上一个值

$num = 当前值

*/
$arr = array(4,5,2,100,3,1,7,100);

function bestChoice($arr){

$min = $e = $L = 0;
for($i=0;$i<sizeof($arr);$i++){
$num = $arr[$i];
if(!isset($s){
$s = $e = $l = $min = $num;
}else{
if($num < $s){
$min = $num;
$L = $num;
continue;
}

if(($num - $min ) > ($e - $s)){
$s = $min;
$e = $num;
}else{
if(($num - $L) > ($e - $s)){
$s = $L;
$e = $num;
}
}
$L = $num;
}
}

var_dump($s,$e);
}

bestChoice($arr);

Answer 5

实现一个复杂度为O(n)的排序算法，找出最小的index，最大的index。

Answer 6

下面是我的思路：
建立2个变量：max_index(表示当前最大元素的索引),max(表示当前的最大元素值)
max_index初始化为最后一个元素索引值，max初始化为最后一个元素值。

从后向前遍历数组，从倒数第二个元素开始：
依次比较当前元素current与max，
将其在数组中更新为max-current；
同时更新max为max与current中的较大者，并更新max_index；
继续向前遍历。

遍历完整个数组之后，此时数组中前面n-1个元素均得到更新。再遍历一遍新数组，得到新数组中除最后一个元素（该元素没有得到更新）之外的最大元素及其索引值(min_index)。索引值就是我们要找的买入号，第一次遍历之后得到的max_index就是卖出号。新数组中的最大值就是差额。

例如初始数组为4 5 2 3 1 7 9，
第一次遍历之后，新数组为5 4 7 6 8 2 9，同时得到max_index为6（从0开始），max为9，
可见除最后一个元素最大元素为8，即第4项（从0开始），即min_index=4，最大差额即为8.

可见，一共对数组进行了2次遍历，同时只需要额外建立3个变量：max，max_index以及最后新数组中的最大之元素索引min_index(按照索引值即可得到最大差额)。满足了时间复杂度和空间复杂度的要求。

请大家指点，希望能看到更高效的算法。

Answer 7

我想的是建立个链表，A存放股票值，B为当天的天数，比如第一天为1.然后再对A值排序，按从小到大顺序排序，然后看头结点与尾节点，如果头结点B值小于尾节点B值，则输出天数值。如果相反，则尾节点减一，再进行判断。

Answer 8

一个整型数组，例如 4 5 2 3 1 7 9

如果每天只允许一种操作 买 或者 卖 或者啥也不干

那么 显然 第一天买入 花费成本是4

第二天卖出 赚取1
显然 买入的要尽量小 卖出的要尽量大 而且受到序列影响

所以就是用序列后面的数减去序列前面的数
5-4 =1
2-4 =-2
3-4 = -1
1-4 = -3
7-4 = 3
9-4 = 5
关于4 可以直接到序列中的任意位置的全部结果
2-5 = -3
3-5 = -2
1-5 = -4
7-5 = 2
9-5 = 1
关于5的全部结果
3-2 = 1
1-2 = -1
7-2 = 5
9-2 = 7
关于2的全部结果
以此方法将除最后一个元素外 全部的元素的结果都算出来

将所有的组合加起来
比如 关于第一个元素的 如果上式中减法的被减数涉及 的 元素就是下一个可以选的元素 他之前的元素的结果 就被忽略了 比如 选择5 那么可以从第二个元素开始再次选择
选择2可以从第三个元素开始选择
选择3可以从第四个元素开始选择
...当然选择是可以的 也可以不选择

这样得到的结果 就是这道题目想要的结果！