动态规划

求最大子数组，最大子乘积

#include <iostream>
#include <vector>
using namespace std;
int max(int a, int b, int c)
{
    return (a > b) ? (a > c ? a : c) : (b > c ? b : c);
}
int min(int a, int b, int c)
{
    return (a < b) ? (a < c ? a : c) : (b< c ? b: c);
}
int pro(vector<int> a)
{
    
    if (a.size() == 0)
        return 0;
    if (a.size() == 1)
        return a[0];
    int p,q;
    p= q = a[0];
    int res = a[0];
    int st1, ed1;
    int st2, ed2;
    st1= ed1 =st2=ed2= 0;
    int res1 = a[0];
    for (int i = 1;i < a.size();i++)
    {
        //p和q代表最大值和最小值
        int temp1 = p;
        int temp2 = q;
        p = max(p*a[i], a[i], temp2*a[i]);//p和q代表当下以n为结尾的最大子数组的值
        q = min(temp1*a[i], q*a[i], a[i]);
        res = (res > p ? res : p);
        res1 = (res1 < q ? res : q);
        if (res == p)
        {
            if (p == a[i])
                st1 = i;
            if (p == temp2*a[i])
                st1 = st2;
            ed1 = i;
        }
        if (res1 == q)
        {
            if (q == a[i])
                st2 = i;
            if (q == temp1*a[i])
                st2 = st1;
            ed2 = i;
        }
        //res1 = (res1 < q ? res : q);
        
    }
    cout << st1 << ed1;
    cout << endl << res1;
    return res;
}

void main()
{
    vector<int> M = { -1,2,3,4,9,-2,5,-3 };
    cout << pro(M);
}