线性查找最大子数组难题,最大子数组难点

2019-05-03 22:25 来源:未知

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

www.weide1946.com 1

问题描述:

示例:

东十八北面的天空.jpg

给定一数组ary,其元素有正有负,寻找ary的和最大的连续子数组,并返回其和。

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_value = nums[0]
        current =0
        for i in range(len(nums)):
            if current > 0: current  =nums[i]
            else:           current =  nums[i]
            if max_value < current:max_value = current
        return max_value

原题:使用如下思想为最大子数组问题设计一个非递归的、线性时间的算法。从数组的左边界开始,由左至右处理,记录到目前为止已经处理过得最大子数组。若已知A[1…j]的最大子数组,基于如下性质将解扩展为A[1…j 1]的最大子数组:A[1…j 1]的最大子数组要么是A[1…j]的最大子数组,要么是某个子数组A[i…j 1] (1≤i≤j 1)。在已知A[1…j]的最大子数组的情况下,可以在线性时间内找到形如A[i…j 1]的最大子数组。

例如数组:

 

思路:题目点出一个很重要的思路就是新数组的最大子数组,必然是2种情况之一:
1.依然是[1,j]数组的最大子数组;
2.[i,j 1]这样一个最大子数组(0<=i<=j 1);
所以关键点就成了,如何去寻找第二种情况:
在解第二种情况的时候,有一点要考虑到,就是如果一段子数组[i,j]的和<0,则最大子数组不可能为[i,j 1],因为sum[i,j 1]<[j 1];
利用这个结论,我们可以对数组进行线性求和,若和<0则抛弃目前计算的子数组,将子数组的和重置为0,顺下去去找新的子数组,左边界的leftIndex也重置为当前index。
若计算中的子数组的和大于目前最大子数组,则更新最大子数字的sum,并更新右边界。
以下是c语言实现代码,复杂度为O(n):

int[] ary = {-3,5,-1,-2,4,-1};
//线性求解最大自数组的问题
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int *linearMaximumSubarray(int arr[], int low, int high); //线性寻找最大子数组

int main()
{
    int arr[16] = {13, -3, -25, 1, -3, 16, 23, 18, -20, -7, -12, -50, -22, 15, -4, 7};
    int *result = linearMaximumSubarray(arr, 0, 15);
    printf("左边界为%d", result[0]);
    printf("右边界为%d", result[1]);
    printf("最大跨界子数组的和为%d", result[2]);
    free(result);
    return 0;
}
//返回最大自数组的左右边界和最大子数组的和
int *linearMaximumSubarray(int arr[], int low, int high)
{
    int *a = calloc(3, sizeof(int));
    int sum = INT_MIN;
    int leftIndex = low;
    int rightIndex = low;
    int subArraySum = 0;
    int subLeftIndex = low;
    for (int i = low; i <= high; i  )
    {
        subArraySum  = arr[i];
        if (subArraySum > sum)
        {
            sum = subArraySum;
            leftIndex = subLeftIndex;
            rightIndex = i;
        }
        if (subArraySum < 0)
        {
            subArraySum = 0;
            subLeftIndex = i   1;
        }
    }

    a[0] = leftIndex;
    a[1] = rightIndex;
    a[2] = sum;
    return a;
}

最大连续子数组为:{5,-1,-2,4},其和为6。

实际上最大子数组问题在算法导论上引申自买股票获最大收益的问题,将来的股票价格会以预期价格的形式给出作为股票购买者的参考价。

数组元素可视为股票价格在某一天相对于前一天的价格的波动,结合例子中的数组,假定股票第0天的价格为50元,第一天的价格波动为-3,那么第一天的股价为47;第二天的价格波动为5(相对第一天),那么第二天的价格为52元,以此类推。。。

低买高卖可获得收益,最大收益的情况为卖出价与买入价之间的价差最大。

在买入和卖出期间的股票的波动价格看做一个子数组,如果能保证某子数组的和为整个数组的所有子数组和最大,那么股票购买者选择在这段时间持有股票可获得最大的收益。

分析:

暴力求解是穷举所有的子数组,寻找和最大的子数组。N个元素的子集问题的规模为2^N,要穷举2^N个子集,复杂度太高。

可以考虑分治算法思想。

将数组ary拆分成左右两个子数组,拆分的方法就是常用mid=(low high)/2的方式。但是,这里的拆分的意义不同于二分查找的拆分,这里拆分是将数组分成左右两个部分,并不存在排除掉ary[mid]的含义。ary[mid]是被划分为左子数组的一部分。

ary的最大子数组必然存在于以下三种情况之一:

A、完全位于左边的子数组:ary[low,mid]

B、完全位于右边的子数组:ary[mid 1,high]

C、跨越了左边和右边的子数组,这种情况的隐含条件在于, 左子数组ary[low,mid]必然至少有一个元素在最大子数组中,也即使可以肯定ary[www.weide1946.com,mid]必然在最大子数组中,否则不满足“跨越”的前提条件而回到情况B;同理,右子数组ary[mid 1,high]必然至少有一个元素在最大子数组中,也即是可以肯定ary[mid 1]必然在最大子数组中。

三种情况的最大子数组必然是这个数组的最大子数组。

遵循以上过程,递归调用求解。

递归基为low与high相等的情况,其含义很明确:单元组的最大子数组必然是其自身。

分治算法实现:

package agother;
import java.util.Arrays;
public class SubArray {
    private static int getMax(int ...ary){
        Arrays.sort(ary);
        return ary[ary.length-1];
    }
    /*最大子数组跨越了左右两个子数组*/
    private static int getMaxSumOfCrossSubArray(int[] ary,int low,int mid,int high){
        int tmpLeftSum = 0,tmpRightSum = 0;
        int leftSum = ary[mid],rightSum = ary[mid 1];//这种情况下,最大子数组至少包含ary[mid]和ary[mid 1]两个元素,才能实现“跨越”
        for (int i = mid; i >= low; i--) {//处理子数组的左边部分
            tmpLeftSum  = ary[i];
            if (leftSum < tmpLeftSum) {
                leftSum = tmpLeftSum;
            }
        }
        for (int j = mid 1; j <= high; j  ) {//处理子数组的右边部分
            tmpRightSum  = ary[j];
            if (rightSum < tmpRightSum) {
                rightSum = tmpRightSum;
            }
        }
        return leftSum rightSum;
    }
    public static int getMaxSumOfSubArray(int[] ary,int low,int high){
        if (high == low) {return ary[low];}//递归基
        int mid = (high low)/2;
        int leftMaxSum =  getMaxSumOfSubArray(ary,low,mid);//最大子数组位于左子数组中
        int crossMaxSum = getMaxSumOfCrossSubArray(ary,low,mid,high);//最大子数组跨越了左右两个子数组
        int rightMaxSum = getMaxSumOfSubArray(ary,mid 1,high);//最大子数组位于左子数组中
        return getMax(leftMaxSum,crossMaxSum,rightMaxSum);
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        try {
            int[] ary = {-3,5,-1,-2,4,-1};
            int result = getMaxSumOfSubArray(ary,0,ary.length-1);
            System.out.println(result);
        } catch (Exception e) {
            // TODO: handle exception
            e.printStackTrace();
        }
    }
}

 

版权声明:本文由韦德娱乐1946_韦德娱乐1946网页版|韦德国际1946官网发布于网络编程,转载请注明出处:线性查找最大子数组难题,最大子数组难点