LeetCode: Maximum Product Subarray && Maximum Subarray &子序列相关

Maximum Product Subarray

Title:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

对于Product Subarray，要考虑到一种特殊情况，即负数和负数相乘：如果前面得到一个较小的负数，和后面一个较大的负数相乘，得到的反而是一个较大的数，如{2，-3，-7}，所以，我们在处理乘法的时候，除了需要维护一个局部最大值，同时还要维护一个局部最小值，由此，可以写出如下的转移方程式：

max_copy[i] = max_local[i]
max_local[i + 1] = Max(Max(max_local[i] * A[i], A[i]), min_local * A[i])

min_local[i + 1] = Min(Min(max_copy[i] * A[i], A[i]), min_local * A[i])

class Solution {

public:

    int maxProduct(vector<int>& nums) {

        int pmin = nums[];

        int pmax = nums[];

        int result = nums[];

        for (int i = ; i < nums.size(); i++){

            int t1= pmax * nums[i];

            int t2= pmin * nums[i];

            pmax = max(nums[i],max(t1,t2));

            pmin = min(nums[i],min(t1,t2));

            result = max(result,pmax);

        }

        return result;

    }

};

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

http://blog.csdn.net/joylnwang/article/details/6859677

http://blog.csdn.net/linhuanmars/article/details/21314059

class Solution{

public:

    int maxSubArray(int A[], int n) {

        int maxSum = A[];

        int sum = A[];

        for (int i = ; i < n; i++){

            if (sum < )

                sum = ;

            sum += A[i];

            maxSum = max(sum,maxSum);

        }

        return maxSum;

    }

};

扩展：子序列之和最接近于0

先对数组进行累加，这样得到同样长度的数组，然后，对数组排序，对排序后的数组相邻的元素相减计算绝对值，并比较大小。

class Solution{

public:

    vector<int> simple(vector<int> nums,int target){

        int min_gap = INT_MAX;

        int index_min ;

        int index_max;

        for (int i = ; i < nums.size(); i++){

            int sum = ;

            for (int j = i; j < nums.size(); j++){

                sum += nums[j];

                if (min_gap > abs(sum-target)){

                    min_gap = abs(sum-target);

                    index_min = i;

                    index_max = j;

                }

            }

        }

        vector<int> result(nums.begin()+index_min,nums.begin()+index_max+);

        return result;

    }

    vector<int> choose(vector<int> nums, int target){

        vector<pair<int,int> > addSums(nums.size());

        addSums[] = make_pair(nums[],);

        for (int i =; i < nums.size(); i++){

            addSums[i] = make_pair(addSums[i-].first + nums[i],i);

        }

        sort(addSums.begin(),addSums.end());

        int min_gap = INT_MAX;

        int index = -;

        for (int i = ; i < addSums.size(); i++){

            int t = abs(addSums[i].first - addSums[i-].first);

            if (min_gap > t){

                min_gap = t;

                index = i;

            }

        }

        int index_min = min(addSums[index].second,addSums[index-].second);

        int index_max = max(addSums[index].second,addSums[index-].second);

        vector<int> result(nums.begin()+index_min+,nums.begin()+index_max+);

        return result;

    }

};

这种做法我没有想到如何扩展到任意的t上面

巴特西

LeetCode: Maximum Product Subarray && Maximum Subarray &子序列相关

Maximum Subarray

最新文章

热门文章