Maximum continuous sub segment sum (dynamic programming, recursive, recursive)

  State Design ：dp[i] Said to a[i] Maximum sequence sum at the end

  State transition equation ： dp[i]=max(a[i],dp[i-1]+a[i]);

/**
     State Design ：dp[i] Said to a[i] Maximum sequence sum at the end 
     State transition equation ： dp[i]=max(a[i],dp[i-1]+a[i]);
*/

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cout << " Enter the number of integers :\n";
    cin >> n;
    cout << " Input  " << n  << "  It's an integer :\n";
    int a[n];
    for(int i=0;i<n;++i)
        cin >> a[i];
    int ans=a[0];
    int dp[n];  //dp[i] Said to a[i] Maximum sequence sum at the end 
    dp[0]=a[0];
    for(int i=1;i<n;++i)
    {
        dp[i]=max(a[i],dp[i-1]+a[i]);
        ans=max(ans,dp[i]);
    }
    cout << ans << endl;
    return 0;
}

Find the maximum continuous subsegment sum of the sequence , If all are negative , Then the maximum continuous maximum field sum is 0
  And also output the start and end subscripts of the maximum sub segment sum

/**
     Find the maximum continuous subsegment sum of the sequence , If all are negative , Then the maximum continuous maximum field sum is 0
     And also output the start and end subscripts of the maximum sub segment sum 
*/

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cout << " Enter the number of integers :\n";
    cin >> n;
    cout << " Input  " << n  << "  It's an integer :\n";
    int a[n];
    for(int i=0;i<n;++i)
        cin >> a[i];
    int ans=0,this_sum=0;
    int sum_start=0,sum_end=0;
    int start=0;
    for(int i=0;i<n;++i)
    {
        this_sum+=a[i];
        if(this_sum>ans)
        {
            ans=this_sum;
            sum_start=start;
            sum_end=i;
        }
        else if(this_sum<0)
        {
            start=i+1;
            this_sum=0;
        }
    }
    cout << "max_sum: " << ans << endl;
    cout << "max_sum_start_index: " << sum_start << endl;
    cout << "max_sum_end_index: " << sum_end << endl;
    return 0;
}

The dichotomy solves , With overlapping subproblems , Using recursion requires some processing operations in the middle .

/**
     The dichotomy solves 
*/

#include <iostream>
#include <cstdio>
using namespace std;
int max_sum(int *a,int l,int r);
int max_sum_3(int *a,int n);
int main()
{
    int n;
    printf(" Enter the number of data :\n");
    cin >> n;
    int a[n];
    printf(" Input %d Number :\n",n);
    for(int i=0;i<n;++i)
    {
        cin >> a[i];
    }
    int sum=max_sum_3(a,n-1);
    cout << sum << endl;
    return 0;
}

// Keep going in two , Until there's only one number , Until the termination condition 
int max_sum(int *a,int l,int r)
{
    if(l==r)
    {
        if(a[l]>0)
            return a[l];
        else
            return 0;
    }
    int mid=l+(r-l)/2;
    int lmax=max_sum(a,l,mid);
    int rmax=max_sum(a,mid+1,r);
    int ltempmax=0,tempsum=0;
    for(int i=mid;i>=l;--i)
    {
        tempsum+=a[i];
        if(tempsum>ltempmax)
            ltempmax=tempsum;
    }
    tempsum=0;
    int rtempmax=0;
    for(int i=mid+1;i<=r;++i)
    {
        tempsum+=a[i];
        if(tempsum>rtempmax)
            rtempmax=tempsum;
    }
    int midmax=ltempmax+rtempmax;
    if(lmax>rmax)
    {
        if(lmax>midmax)
            return lmax;
    }
    else
    {
        if(rmax>midmax)
            return rmax;
    }
    return midmax;
}

int max_sum_3(int *a,int n)
{
    return max_sum(a,0,n-1);
}