练习4.1-2 暴力求解最大子数组

问题描述：

股票低价买进，高价卖出。我们不从每日价格的角度来看待输入数据，而是考察每日价格变化。

如数组A[13 -3 -25 20 -3 -16 -23 18 20 -7 12 -5 -22 15 -4 7]，问题转换为寻找数组A的和最大非空连续子数组。用暴力求解的方法该子数组。

解题思路：

暴力求解没什么好说的，寻找数组A每一种的连续子数组，并计算其和，寻找和的最大值。

具体代码：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 int dp[100][100] = { 0 };
 4 int stock[100] = { 0 };
 5 int from, to;
 6 int max = -1000;
 7 
 8 int findMax(int start, int end){
 9      if (dp[start][end] != 0){
10            if (dp[start][end] > max){
11                 max = dp[start][end];
12                 from = start - 1;
13                 to = end;
14            }
15            return dp[start][end];
16      }
17      for (int i = start; i < end; i++){
18            dp[i][end] = findMax(i, end - 1) + findMax(end,end);
19            if (max<dp[i][end]){
20                 max = dp[i][end];
21                 from = i-1;
22                 to = end;
23            }
24      }
25      return dp[start][end];
26 }
27 
28 int main(){
29      int days;
30      scanf("%d", &days);
31      for (int i = 1; i <= days; i++){
32            scanf("%d", &stock[i]);
33            dp[i][i] = stock[i];
34      }
35      int x=findMax(1, days);
36      printf("%d %d %d %d", max, from, to,x);
37      return 0;
38 }

做题感悟：从今天开始做算法导论的笔记和博客，贵在坚持吧。