MaximumSubArray – Dynamic programming

//aim of the program is to find the maximum subarray (contiguous sequence of number) in an array containing both positive and negative numbers

#include<iostream>
using namespace std;
int main(){
    int n;
    cout<<“enter the number of elements”;
    cin>>n;
    int arr[n],max[n],maxsum=0;
    cout<<“enter the elements”;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    if(arr[0]>0)
      max[0]=arr[0];
      else
      max[0]=0;
      for(int i=1;i<n;i++){
          if((max[i-1]+arr[i])>0){
              max[i]=max[i-1]+arr[i];
          }
              else
              max[i]=0;
          
      }
      for(int i=1;i<n;i++){
          if(max[i]>maxsum){
              maxsum=max[i];
          }
      }
      cout<<“\n maximun sum is “<<maxsum;
  }
 

Change Making problem-Dynamic Programming

Problem:

Given a value n, if we want to make change for n cents, and we have infinite supply of each of d = { d1, d2, .. , dm} valued coins, what is the minimum number of coins to make the change?

 

	#include<iostream>
	using namespace std;
	int d[4]={1,2,5,10};//denomination array
	int k=4;//number of denomination
	void getMinimumNumberOfChanges(int n){
	//c[i] => array to store the minimum number of coins required to value i
	//s[i] => array to store the last coin required to get the value i
	int c[n],s[n],min,coin;
	c[0]=0;
	//DP is all about splitting in the problem into many sub problems
	//here we first find no. of changes for p=1 then ,p=2 ,......till p= n which is the required value
	//so first for loop runs from p=1 to n
	for(int p=1;p<=n;p++){
	min=999;
	considering all possible denominations from array index 0 to k-1
	for(int i=0;i<k;i++){
	if(d[i]<=p){
	if(1+c[p-d[i]]<min){
	min=1+c[p-d[i]];
	coin=i;
	}
	}
	}
	c[p]=min;
	s[p]=coin;
	}
	cout<<"Minimum no. of coins required "<<c[n];
	cout<<"coins are"<<'\n';
	//this while loop is for tracing the coins.the code is self explanatory
	while(n>0){
	cout<<d[s[n]]<<"\n";
	n=n-d[s[n]];
	}
	}

view raw changemaking.cpp hosted with ❤ by GitHub