use the greedy algorithm to gain the best benefits

use the greedy algorithm to gain the best benefits

 1. dynamic programming solution

2. greedy algorithm solution 

 

The outputs corresponding to greedy algorithm: 

Input the length of array: 16
  1  6  1  6  2  4  2  1  2  6  7  4  8  7  4  7
max_profit: 25

 corresponding codes:

//step_1 generate a random array with random values
// step_2 suppose the value in array is prices of a specific prices
// step_3 write a function to get your most profit
#include 
#include 
#include 
#include 
using namespace std;
void generate_array(int *&arr, int len);
void display_array(int arr[], int len);
int greedy_solution(int arr[], int len);
int dp_solution(int arr[], int len);
int main()
{
    srand((unsigned)time(NULL));
    cout << "Input the length of array: ";
    int len;
    cin >> len;
    int *a;
    generate_array(a, len);
    display_array(a, len);
    int max_profit = greedy_solution(a, len);
    //int max_profit = dp_solution(a, len);
    cout << "nmax_profit: " << max_profit << endl;
    free(a);
    return 0;
}
void generate_array(int *&arr, int len)
{
    arr = new int[len];
    for (int i = 0; i < len; i++){
        arr[i] = rand() % 8 + 1;
    }
}
void display_array(int arr[], int len)
{
    for (int i = 0; i < len; i++) {
        cout << setw(3) << arr[i] ;
    }
}
int greedy_solution(int arr[], int len)
{
    int max_profit = 0;
    for (int i = 1; i < len; i++) {
        if (arr[i] > arr[i-1]){
            max_profit += (arr[i] - arr[i-1]) ;
        }
    }
    return max_profit;
}

The outputs from two different algorithms:

Input the length of array: 5
  8  8  1  7  7
max_profit from greedy_solution : 6
max_profit from dp_solution : 6

The corresponding solutions:

//step_1 generate a random array with random values
// step_2 suppose the value in array is prices of a specific prices
// step_3 write a function to get your most profit
#include 
#include 
#include 
#include 
using namespace std;
void generate_array(int *&arr, int len);
void display_array(int arr[], int len);
int greedy_solution(int arr[], int len);
int dp_solution(int arr[], int len);
int main()
{
    srand((unsigned)time(NULL));
    cout << "Input the length of array: ";
    int len;
    cin >> len;
    int *a;
    generate_array(a, len);
    display_array(a, len);
    int max_profit_1 = greedy_solution(a, len);
    int max_profit_2 = dp_solution(a, len);
    cout << "nmax_profit from greedy_solution : " << max_profit_1 << endl;
    cout << "max_profit from dp_solution : " << max_profit_1 << endl;
    free(a);
    return 0;
}
void generate_array(int *&arr, int len)
{
    arr = new int[len];
    for (int i = 0; i < len; i++){
        arr[i] = rand() % 8 + 1;
    }
}
void display_array(int arr[], int len)
{
    for (int i = 0; i < len; i++) {
        cout << setw(3) << arr[i] ;
    }
}
int greedy_solution(int arr[], int len)
{
    int max_profit = 0;
    for (int i = 1; i < len; i++) {
        if (arr[i] > arr[i-1]){
            max_profit += (arr[i] - arr[i-1]) ;
        }
    }
    return max_profit;
}
int dp_solution(int arr[], int len)
{
    int dp_0 = 0;
    int dp_1 = -arr[0];
    for (int i = 1; i < len; i++){
        dp_0 += max(dp_0, dp_1 + arr[i]);
        dp_1 += max(dp_1, dp_0 - arr[i]);
    }
    return dp_0;
}