一个节省空间的小技巧

我们往往习惯将运算过程的临时结果存储起来，这样的思想比较容易理解也是惯性的思维，然而往往大多数情况下我们不需要存储中间过程的变量。

这里举一个例子，杭电OJ的1003题MaxSum，虽然同时采用暴力求解，但是中间的sum结果不采用二维数组存储而只是简单的通过每次置0后重新计算这样就可以节省空间。

虽然超时了，但是还是将代码粘贴下来，来警醒自己该丢弃的丢弃，不要有惯性思维。

  1 /*1003 maxSum
  2 解决方案：类动态规划
  3 结果：超时
  4 */
  5 #include <stdio.h>
  6 #include <stdlib.h>
  7 #include <string.h>
  8 
  9 #define NUM_LENGTH 100000 + 100
 10 
 11 int main()
 12 {
 13 　　int num_case,num_len;
 14 　　int num[NUM_LENGTH];
 15 　　//int sum[NUM_LENGTH][NUM_LENGTH];
 16 　　int i,j,k,maxSum,start,end,thisSum;
 17 　　scanf("%d",&num_case);
 18 
 19 for(i = 1; i <= num_case; i++)
 20 {
 21　　 scanf("%d",&num_len);
 22 　　memset(num,0,sizeof(num));
 23 　　//memset(num,0,sizeof(sum));
 24　　 /*
 25 　　for(j = 0;j < num_len; j++)
 26 　　for( k = 0; k < num_len; k++)
 27 　　{
 28 　　　　sum[j][k] = 0;
 29　　 }
 30 　　*/
 31 
 32 　　for(j = 0; j < num_len; j++)
 33 　　{
 34 　　　　scanf("%d",&num[j]);
 35 　　}
 36 
 37　　 /*
 38　　 for(j = 0; j < num_len; j++)
 39 　　{
 40 　　　　sum[j][j] = num[j];
 41 　　}
 42 　　*/
 43 
 44 　　//maxSum = sum[0][0];
 45 　　maxSum = num[0];
 46 　　start = 0;
 47 　　end = 0;
 48 
 49 　　for( j = 0; j < num_len - 1; j++ )
 50 　　{
 51 　　　　thisSum = 0; //通过每次重新设置求和的值来进行优化存储空间
 52 　　　　for( k = j; k < num_len - 1; k++ )
 53 　　　　{
 54 　　　　　　thisSum += num[k]; //在此处进行优化，用临时变量存储当前求和而不是用二维数组永久存储
 55 
 56 　　　　　　if(thisSum > maxSum)
 57 　　　　　　{
 58 　　　　　　　　maxSum = thisSum;
 59 　　　　　　　　start = j + 1;
 60 　　　　　　　　end = k + 1;
 61 　　　　　　}
 62 　　　　}
 63 　　}
 64　　 /*
 65　　 if(sum[num_len - 1][num_len - 1] > maxSum)
 66　　 {
 67　　　　 maxSum = sum[num_len - 1][num_len - 1];
 68　　　　 start = num_len;
 69　　　　 end = num_len;
 70 　　}
 71 　　*/
 72 
 73 　　printf("Case %d:
",i);
 74 
 75 　　if(i != num_case)
 76 　　　　printf("%d %d %d

",maxSum,start,end);
 77 　　else
 78 　　　　printf("%d %d %d",maxSum,start,end);
 79 
 80 　　}
 81 }
 82 
 83  
 84 
 85 顺便贴一下某位大神写的AC的DP代码：
 86 
 87 #include<iostream>  
 88 using namespace std;  
 89 #define Min -999999  
 90 int main()  
 91 {  
 92     int data[100000],start,end;  
 93     int m;  
 94     int step=1;  
 95     cin>>m;      
 96     while(m--)  
 97     {  
 98         int n;  
 99         cin>>n;  
100         for (int i=1; i<=n;i++)  
101             cin>>data[i];  
102         int max = Min;  
103         int k=1;  
104         int sum = 0;  
105         for (i=1; i<=n; i++)  
106         {  
107             sum = sum + data[i];  
108             if (sum > max)  
109             {  
110                 max = sum;  
111                 start=k;  
112                 end=i;  
113             }  
114             if(sum<0)  
115             {  
116                 sum=0;  
117                 k=i+1;  
118             }  
119         }  
120         if(step!=1)  
121             cout<<endl;  
122         cout<<"Case "<<step<<":"<<endl;  
123         cout<<max<<" "<<start<<" "<<end<<endl;  
124         step++;  
125     }  
126     return 0;  
127 }

我是一块砖，哪里需要往哪搬。