OJ题目7--数组元素的局部选择和抛弃问题

对于常规的求出数组中差值最大的两个元素及二者的差值时，对数组进行一次遍历，分别动态存储数组中当前的最大及最小值即可。但很多情况下，实际中的数据也可以抽象成一个数组，但是问题却要比简单的找出最大差值要复杂一些，因为根据实际情况，对问题的求解会有诸多条件。比如股票的买卖，买入股票的时间一定要早于卖出股票的时间。这时就不能把范围扩大到整个数组中，而是在当前数字的后面。

1，

本题的解题思路：我想要股票获得更大的利润，就要尽可能的在股票价格低的时候买入，价格高的时候卖出，而且买入时间一定要早于卖出时间（体现在记录价格的数组中就是买入结点的下标一定要早于卖出结点的下标）。在从第一个结点到最后一个结点遍历的过程中，我要随时留心，记录所遍历到的结点中出现的最下结点，如果一个结点比之前所有的结点都要小，那就把它记录下来，并用它更新最小结点的数值，如果遍历到的结点大于之前记录的最小结点，那在此结点将股票售出就会获利，只不过是多少的问题，此时需要将两者只差与原先的最大利润值相比较。总结起来的话就是每当遍历到一个结点时，不是用该结点去更新最小值，就是用该节点与原先的最小值相减，尝试更新最大值。这样，最小值（即潜在的买入结点），永远在最大值（即潜在的卖出结点）之后。

int maxProfit(int* prices, int pricesSize)
{
    int miniprices=prices[0];
    int maxret=0;
    int i=0;
    for(i=0;i<pricesSize;i++)
    {
        if(prices[i]<miniprices)
        {
            miniprices=prices[i];
        }
        else
        {
            maxret=(maxret<(prices[i]-miniprices))?prices[i]-miniprices:maxret;
        }
    }
    return maxret;
}

2，

本题要求找到数组中差值最大的两个元素，但是额外有一点要求，较小的元素必须要在较大的元素之前。

那么本题的思路就很明确了，首先从第一个元素开始，如果该元素的下一个元素比它大，那求出二者的差值。反之如果该元素的下一个元素比它小，则这个元素一定不会是最终选定相减的两个元素之一，因为无论后面出现了什么样的元素，当前的两个元素而言，一定是较小的那个元素做减数更合适，所以排在前面的更大的元素就应该跳过。

int compare(int a,int b)
{
    return a>b?a:b;
}
int maximumDifference(int* nums, int numsSize)
{
    int num=-1;
    int cur=nums[0];
    for(int i=1;i<numsSize;i++)
    {
        if(cur<nums[i])
        {
            num=compare(num,nums[i]-cur);
        }
        else
        {
            cur=nums[i];
        }
    }
    return num;
}

3,

本题思路：当计算到某一节点时，如果该节点之前的所有节点的和为负数，说明这些节点对于总和来讲是累赘，丢弃它们对我找最大值的目的而言绝对没有坏处。同时要注意的是，由于sum的值在不断变化，而且sum的最大值不一定出现在哪个地方，所以要额外定义一个变量max随时记录sum的最大值。（这道题也是体现研究数组局部问题的典型）

int maxSubArray(int* nums, int numsSize)
{
    int i=0;
    int sum=0;
    int max=-10000;
    for(i=0;i<numsSize;i++)
    {
        if(sum>0)
        {
            sum+=nums[i];
        }
        else
        {
            sum=nums[i];
        }
        max=max>sum?max:sum;
    }
    return max;
}