Question

1. Use the dynamic programming approach to write an algorithm to find the maximum sum in any contiguous sublist of a given list of n real values. Analyze your algorithm, and show the results using order notation.

Answer 1

Algorithm:

->

Initialize:

-MAX=a[0]

-CURRENT MAX=0

-LOOP:

-for each element of array starting from 1 to end of array

      current max=(find maximum from either (array[i]) or (CURRENT MAX+array[i])

       MAX=find maximum from (CURRENT MAX) or (CURRENT MAX + MAX)

end loop

print MAX is answer

STEPS:

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

PROGRAM:

#include<bits/stdc++.h>
using namespace std;

int main()
{
   int n;
   cout<<"Enter the size of array:";
   cin>>n;
   int a[n];
   for(int i=0;i<n;i++)
       cin>>a[i];
      
int MAX = a[0];
int CURRENT_MAX = a[0];

for (int i = 1; i < n; i++)
{
       CURRENT_MAX = max(a[i], CURRENT_MAX+a[i]);//check weather previous step is greater or CURRENT_MAX+rray[i]
      
       MAX = max(MAX, CURRENT_MAX); //MAximise MAX with either previous MAX or CURRENT_MAX
      
}
cout<<MAX;
}

OUTPUT: