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

UI设计界面 UI设计界面 主题:1059 回复:2190

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

晚风撩人 发布于 2016-11-14 字数 294 浏览 965 回复 8

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

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

评论(8

浮生未歇 2017-10-05 8 楼

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

清晨说ぺ晚安 2017-10-05 7 楼

这是个很经典的动态规划算法
很显然要让利益最大化,每天结束后要么全仓持有股票,要么空仓持有现金。
记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]的金额一定不足一股,因此股票数较大的总资产一定比较大;股票数相等时再比较剩余现金

甜柠檬 2017-08-24 6 楼

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表示什么时候卖出

归属感 2017-05-21 5 楼

<?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&lt;sizeof($arr);$i++){
     $num = $arr[$i];
     if(!isset($s){
             $s = $e = $l = $min = $num;
     }else{
            if($num &lt; $s){
                 $min = $num;
                 $L = $num;
                 continue;
            }

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

 var_dump($s,$e);

}

bestChoice($arr);

浮生未歇 2017-04-28 4 楼

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

浮生未歇 2017-04-28 3 楼

下面是我的思路:
建立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(按照索引值即可得到最大差额)。满足了时间复杂度和空间复杂度的要求。

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

偏爱自由 2017-04-21 2 楼

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

归属感 2017-02-05 1 楼

一个整型数组,例如 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可以从第四个元素开始选择
...当然选择是可以的 也可以不选择

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