最大子序和

/*
最大子序和。
动态规划：
1、状态定义
2、状态初始化
3、状态转移
*/
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<iostream>
int getMax(int a,int b){
    if(a>b)
        return a;
    return b;
}
int maxSubArray(int* nums, int numsSize){
    if(numsSize<=0)
        return 0;
    int dp[numsSize],rs,i;
    dp[0]=rs=nums[0];
    for(i=1;i<numsSize;i++){
        dp[i]=getMax(dp[i-1],0)+nums[i];
        rs=getMax(dp[i],rs);
    }
    return rs;
}
int maxSubArray1(int* nums, int numsSize){
    if(numsSize<=0)
        return 0;
    int rs,temp,i;
    rs=temp=nums[0];
    for(i=1;i<numsSize;i++){
        temp=getMax(temp,0)+nums[i];
        rs=getMax(temp,rs);
    }
    return rs;
}
int main()
{
    int nums[]={-2,1,-3,4,-1,2,1,-5,4};
    int rs=maxSubArray1(nums,9);
    printf("%d
",rs);
    return 0;
}