首页 > 编程语言 > 详细

45 最大子数组差

时间:2018-05-24 23:24:36      阅读:279      评论:0      收藏:0      [点我收藏+]

原题网址:https://www.lintcode.com/problem/maximum-subarray-difference/description

描述

给定一个整数数组,找出两个不重叠的子数组A和B,使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。

返回这个最大的差值。

子数组最少包含一个数

您在真实的面试中是否遇到过这个题?  

样例

给出数组[1, 2, -3, 1],返回 6

挑战

时间复杂度为O(n),空间复杂度为O(n)

 

思路:两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大,即是说其中一个最大,另一个最小。

顺着最大子数组Ⅱ的解法,定义四个数组leftMax,leftMin,rightMax,rightMin,分别保存0~i的最大子数组和、最小子数组和以及i+1~n-1的最大子数组和、最小子数组和;

遍历,计算leftMax - rightMin 与 rightMax - leftMin 的最大值,将两者中较大的一个return出去。

 

AC代码:

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: An integer indicate the value of maximum difference between two substrings
     */
    int maxDiffSubArrays(vector<int> &nums) {
        // write your code here
        int n=nums.size();
     if (n==0)
     {
         return 0;
     }
     vector<int> leftMax(n,0);
     vector<int> leftMin(n,0);
     vector<int> rightMax(n,0);
     vector<int> rightMin(n,0);
     int i=0,tempsum1,tempsum2,maxsum,minsum;

     leftMax[0]=leftMin[0]=maxsum=minsum=nums[0];
     tempsum1=tempsum2=0;
     for (i=0;i<n;i++)
     {
         tempsum1+=nums[i];
         tempsum2+=nums[i];
         if (tempsum1>maxsum)
         {
             maxsum=tempsum1;
         }
         if (tempsum1<0)
         {
             tempsum1=0;
         }
         if (tempsum2<minsum)
         {
             minsum=tempsum2;
         }
         if (tempsum2>0)
         {
             tempsum2=0;
         }
         leftMax[i]=maxsum;
         leftMin[i]=minsum;
     }

     rightMax[n-1]=rightMin[n-1]=maxsum=minsum=nums[n-1];
     tempsum1=tempsum2=0;

     for (i=n-1;i>0;i--)
     {
         tempsum1+=nums[i];
         tempsum2+=nums[i];
         if (tempsum1>maxsum)
         {
             maxsum=tempsum1;
         }
         if (tempsum1<0)
         {
             tempsum1=0;
         }
         if (tempsum2<minsum)
         {
             minsum=tempsum2;
         }
         if (tempsum2>0)
         {
             tempsum2=0;
         }
         rightMax[i-1]=maxsum;
         rightMin[i-1]=minsum;
     }

     int diff1=leftMax[0]-rightMin[0];
     int diff2=rightMax[0]-leftMin[0];
     for (i=1;i<n-1;i++)
     {
         if (leftMax[i]-rightMin[i]>diff1)
         {
             diff1=leftMax[i]-rightMin[i];
         }
         if (rightMax[i]-leftMin[i]>diff2)
         {
             diff2=rightMax[i]-leftMin[i];
         }
     }
     int diff=max(diff1,diff2);
     return diff;
    }
};

 

 

 

 

45 最大子数组差

原文:https://www.cnblogs.com/Tang-tangt/p/9085570.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!