4.1-2
use brute-force to solve the maximum_subarray problem.
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include<limits.h>
using namespace std;
void max_subarray(int A[], int low, int high)
{
int profit = INT_MIN;
int day1, day2;
int i, j;
for(i = low; i < high; i++)
{
for(j = i + 1; j <= high; j++)
{
if((A[j] - A[i]) > profit)
{
profit = A[j] - A[i];
day1 = i;
day2 = j;
}
}
}
cout<<"profit is:"<<profit<<endl;
cout<<"choose day:"<<day1<<" "<<day2<<endl;
}
void main()
{
int A[] = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97};
max_subarray(A, 0, 15);
}
4.1-3
这个问题的英语描述还是很让我费解的：what problem size n0 gives the crossover point at which the recursive algorithm beats the brute-force algorithm?
4.1-5
代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include<limits.h>
using namespace std;
int max_subarray(int A[], int j, int& sub_low, int& sub_high)
{
int profit;
if(j == 0)
{
sub_low = sub_high = j;
profit = A[j];
return profit;
}
else
{
int sum1, sum2;
int sum3 = 0;
int sub_low1, sub_high1;
int sub_low3;
sum1 = max_subarray(A, j - 1, sub_low, sub_high);
sub_low1 = sub_low;
sub_high1 = sub_high;
sum2 = A[j];
if(sum2 > 0)
{
int sum = 0;
sum3 = INT_MIN;
for(int i = j; i >= 0; i--)
{
sum += A[i];
if(sum3 < sum)
{
sum3 = sum;
sub_low3 = i;
}
}
}
if(sum1 >= sum2 && sum1 >= sum3)
{
sub_low = sub_low1;
sub_high = sub_high1;
profit = sum1;
return profit;
}
else if(sum2 >= sum1 && sum2 >= sum3)
{
sub_low = sub_high = j;
profit = sum2;
return profit;
}
else
{
sub_low = sub_low3;
sub_high = j;
profit = sum3;
return profit;
}
}
}
void main()
{
int A[] = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97};
int B[16];
for(int i = 1; i <= 16; i++)
{
B[i - 1] = A[i] - A[i - 1];
}
int a, b;
int& sub_low = a;
int& sub_high = b;
cout<<max_subarray(B, 15, sub_low, sub_high)<<endl;
cout<<a<<endl;
cout<<b<<endl;
}