首页 > 代码库 > 一天一道算法题--6.25--无定义

一天一道算法题--6.25--无定义

2024-07-09 20:40:02   223人阅读

感谢微信平台---一天一道算法题--每天多一点进步----

其实今天我接下去补上的几题都来自---待字闺中 所以我就原封不动的将它的题目与分析搬过来了

原题

给定一个数组，我们可以找到两个不相交的、并且是连续的子数组A和B，A中的数字和为sum(A), B中的元素和为sum(B)。找到这样的A和B，满足sum(A) - sum(B)的绝对值是最大的。 例如：[2, -1 -2, 1, -4, 2, 8]划分为A=[-1, -2, 1, -4], B=[2, 8]， 最大的值为16

分析

如果没有比较丰富的经验，这个题目咋一看，有一种不明觉厉的感觉。但只要逐层分析，就可以看到，其实只要分析两层就可以了。首先我们来看看题目有哪些要点（明确题意，有不清楚的，一定要澄清。）：

子数组是不相交的

子数组是连续的，这个有点多余，但还是强调一下得好

然后题目的要求是，差的绝对值最大。那我们自然而然能够想到：找到的两个不相交的子数组，一个值要很小，一个值要 很大。这样才能够保证差的绝对值最大。那如何找到这样的数组呢？我们从不相交的这个条件入手。看题目中例子（从简单的例子出发，发现解决方案，是面试中常 用技巧。切记！）：

013456
2-11428

看 上面的表格，如果两个子数组不想交，我们有六个位置，作为划分的备选，0和1之间、1和2之间、2和3之间，...，直到5和6之间。这六个位置，都可以 将数组划分为两部分。我们设定，数组长度为n，i将数据划分为两部分分别为 [0,i-1]和[i,n-1]。都是两边包含的集合。i是从1到n-1的。

对 于任意的i，我们得到了两部分[0, i-1]和[i, n-1]。接下来，就是在这两部分中，找到一个和最小的子数组A，以及和最大的子数组B。那么A-B的绝对值，就是i这个划分下，满足条件的两个数组的差 的最大值。对于，所有的i而言，这个绝对值最大时的A和B就是我们要找到的。

思 路通顺了，接下来要确定，找到在i处划分，和最大以及和最小的子数组的方法。这里，就要使用到，我们前几天分享的动态规划的思想。那篇文章，大家好好阅读 分析了么。相信一定能够给大家带来很多的启发。回到这个题目，我们单独的考虑，给定一个数组，求和最大的子数组以及和最小的子数组。

先 分析和最大的子数组，这个问题，是比较经典的问题了，但是我们这里要处理的是，求得每一个i左侧的最大连续子数组。作如下分析，假设数组为X, 假设max_until[i]表示，以i位置结尾的连续子数组的最大和。max_until[i]和max_until[i-1]是什么关系呢？

  1. 如 果X[i] + max_until[i - 1] > max_until[i - 1] and X[i] + max_until[i - 1] > X[i]。那么X[i]应该加入到连续子数组中，max_until[i] = max_until[i-1] + X[i].

  2. 否则max_until[i] = X[i]，连续子数组只有一个元素。

但 是，我们要的并不是以i结尾的子数组，尽管给的例子中是这样的，我们要的是i之前的所有连续子数组中，和最大的。并不一定包括i。要如何处理呢？我们再开 辟子数组max_left[i]表示[0,i]中连续子数组的最大值。那这个值要如何求得呢？我们在遍历数组，求得max_until[i]的时 候，max_left[i]只需要在max_until[i]和此前保存的最大值里取最大的即可。也就是一次遍历，就可以完全求得max_until数组 和max_left数组。同理可以求得min_until以及min_left数组。

这是处理的划分的左半部分。那么右半部分呢？

右半部分的思路也是一样的，只不过，我们在遍历数组的时候，需要从右向左进行遍历。

总结整个方法的流程如下：

  1. 从左向右遍历数组，计算max_left和min_left数组，O(n)时间复杂度

  2. 从右向左遍历数组，计算max_right和min_right数组，O(n)时间复杂度

  3. 然后对于每一个i，i从1开始到n-1,计算max_left[i - 1] - min_right[i], max_right[i] - min_left[i - 1]。选取绝对值最大的。

方法的整体空间复杂度为O(n),时间复杂度也是O(n)。

 

//贴的代码   来自-----sysu_arui

我这几天忙于期末考没时间额 今天win8系统网络能正常连接 网页无法打开各种qq游戏无法玩不知道出神马问题了..........

准备重装win7win8

太烦了

  1 #include <assert.h>  2 #include <stdlib.h>  3 #include <limits.h>  4 #define N 100  5   6 int max(int num1, int num2)  7 {  8 return num1 > num2 ? num1 : num2;  9 } 10  11 int min(int num1, int num2) 12 { 13 return num1 < num2 ? num1 : num2; 14 } 15  16 int max_difference(int *array, int n) 17 { 18 int *max_left = (int*)malloc(sizeof(int) * n); 19 int *min_left = (int*)malloc(sizeof(int) * n); 20 int *max_right = (int*)malloc(sizeof(int) * n); 21 int *min_right = (int*)malloc(sizeof(int) * n); 22 //initialize 23 int max_left_until = array[0]; 24 int min_left_until = array[0]; 25 max_left[0] = array[0]; 26 min_left[0] = array[0]; 27 //calculate max_left and min_left 28 for(int i=1; i<n; i++) 29 { 30 if(max_left_until > 0) 31 max_left_until += array[i]; 32 else 33 max_left_until = array[i]; 34 if(min_left_until < 0) 35 min_left_until += array[i]; 36 else 37 min_left_until = array[i]; 38 max_left[i] = max(max_left[i-1], max_left_until); 39 min_left[i] = min(min_left[i-1], min_left_until); 40 } 41 //print max_left and min_left 42 printf("\n max_left = "); 43 for(int i=0; i<n; i++) 44 { 45 printf("%d ", max_left[i]); 46 } 47 printf("\n min_left = "); 48 for(int i=0; i<n; i++) 49 { 50 printf("%d ", min_left[i]); 51 } 52 //initialize 53 int max_right_until = array[n-1]; 54 int min_right_until = array[n-1]; 55 max_right[n-1] = array[n-1]; 56 min_right[n-1] = array[n-1]; 57 //calculate max_right and min_right 58 for(int i=n-2; i>=0; --i) 59 { 60 if(max_right_until > 0) 61 max_right_until += array[i]; 62 else 63 max_right_until = array[i]; 64 if(min_right_until < 0) 65 min_right_until += array[i]; 66 else 67 min_right_until = array[i]; 68 max_right[i] = max(max_right[i+1], max_right_until); 69 min_right[i] = min(min_right[i+1], min_right_until); 70 } 71 //print max_right and min_right 72 printf("\n max_right = "); 73 for(int i=0; i<n; i++) 74 { 75 printf("%d ", max_right[i]); 76 } 77 printf("\n min_right = "); 78 for(int i=0; i<n; i++) 79 { 80 printf("%d ", min_right[i]); 81 } 82 int max_diff = INT_MIN; 83 for(int i=1; i<n; ++i) 84 { 85 int temp = max(max_left[i-1] - min_right[i], 86 max_right[i] - min_left[i-1]); 87 if(temp > max_diff) 88 max_diff = temp; 89 } 90 free(max_left); 91 free(min_left); 92 free(max_right); 93 free(min_right); 94 return max_diff; 95 } 96  97 int main(int argc, char **argv) 98 { 99 //a = 7 2 -1 -2 1 -4 2 8100 int a[N];101 int n; //actual array size102 while(scanf("%d", &n) != EOF)103 {104 for(int i=0; i < n; ++i)105 {106 scanf("%d",&a[i]);107 }108 printf("\n max_difference = %d\n", max_difference(a, n));109 }    110 return 0;111 }
View Code

 

today:

　　甜蜜的牵手是短暂的

　　分手的痛苦是永恒的

　　来自------分手大师

　　个人观点不要因此而

　　不敢去残害小姑娘啊

 

 

 

 

 


联系
我们