//计算数组中任何连续子数组的最大和，并打印最大子数组(求开始和结束下标)
//思路：1：当数组元素全为0时，输出最大的那个负数
//      2：当数组有正有负时，i=0遍历数组，从大于0的那个元素开始，记录此时的下标为shart（最大子数组起始下标），从start开始遍历剩下的元素，若元素和num大于max的值则更新max，
//    且将此时的下标赋值给end（最大子数组终止下标），当num小于0则说明后面出现的（如果出现）最大子数组不可能包含这些元素，所以退出内层循环，继续外层循环，找下一个大于
//    0的数组元素，且外层循环的i变量此时变为temp+1，继续下面的循环。注意内层循环当temp>=length时，说明内层循环已经把所有数组元素都遍历结束，所以外层循环可以直接break。
//         
#include <stdio.h>
#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;
 
int getmax(int data[],int length)
{
    int temp=0,start=0,end=0,i=0,num=0,max=0,flag=0;
    while(i<length)
    {
        if(data[i]>0)
        {
            temp=i;
            while(temp<length)
            {
                num+=data[temp];
                
                if(num<0)   //当num<0时退出这个循环
                {
                    num=0;
                    i=temp+1;
                    break;
                }
                
                if(num>max) //不加=说明若存在多个最大子数组时取第一个，加上=说明取最后一个
                {
                    start = i;
                    max=num;
                    end = temp;
                    //cout<<i<<" "<<temp<<endl;
                    
                }
                temp++;
            }
            if(temp>=length) //当temp已经循环到数组最后一位，则结束整个外层循环
                break;  
        }
        else
        {
            i++;
            flag++;  //用来记录负数出现的次数
        }
    }
    if(flag==length) //数组全为负数的情况
    {
        int max=data[0];
        for(i=1;i<length;i++)
        {
            if(data[i]>max)
            {    
                max=data[i];
            }    
        }
        return max;
    }
    
    for(i=start;i<=end;i++)  //打印最大子数组
        cout<<data[i]<<" ";
    cout<<endl;
    return max;
}
//更简单的写法，没有输出下标
int findmax(vector<int> ve)
{
	if (ve.size() == 0)
		return 0;
	int i = 0,sum=0,great=INT_MIN;
	for (i = 0; i < ve.size(); i++)
	{
		if (sum <= 0)
			sum = ve[i];
		else
			sum += ve[i];
		if (sum > great)
			great = sum;
	}
	
	return great;
}
 
int main()
{
    
    int data[] = {-32, -10, 33, -23, 32, -12, 41, -12, 1, 3, 5, -98, 70, -21, 10, -9, 61};
    int length = sizeof(data) / sizeof(int);
    
    cout<<getmax(data,length)<<endl;
    
	system("pause");
}