剑指offer42：连续数组的最大和 leecode303:区域和检索

方法1：动态规划

C：

int maxSubArray(int* nums, int numsSize){
	
    int count=0;
    int addmax=nums[0];
    for(int i=0;i
        count+=nums[i]; 
        if(addmax
            addmax=count;
        }
        if(count<0)
        {
            count=0;
        }
    }
    return addmax;
}

C++

class Solution {
public:
    int maxSubArray(vector& nums) {
        int addmax=nums[0];
        int count=0;
        for(int val:nums)
        {
            count=max(count+val,val);//每次累加得到新的count;
            addmax=max(count,addmax);//每次得到的count和保存的最大和做比较；
          
        }
        return addmax;
    }

};

方法2：分治（用到的是递归的思想 ，我还不会做。）

在这里插入代码片

using namespace std;
class NumArray {
public:
	vectorpresum;

	NumArray(vector& nums) {
		int n = nums.size();
		presum[0]= 0 ;
		presum.resize(n + 1);
		for (int i = 0; i < n; ++i)
		{
			presum[i + 1] = nums[i] + presum[i];
		}
	}

	int sumRange(int left, int right) {
		return presum[right + 1] - presum[left];
	}

};
int main()
{
	vectornums{-2,1,-3,4,1};
	NumArray numarry(nums);
	
	int x=numarry.sumRange(0, 2);
	cout << x << endl;
}

此代码用到的方法是前缀和。

nums是被索引的数组，presum记录累加和。

有此辅助容器，我们在查询时就不用再次遍历，调用这个函数的时间复杂度为 O（1）。

注意这个代码：presum[0]= 0 ; 在本代码中可以不写，因为我们辅助开辟的presum容器的0号下标元素默认是0；如果写了，就要考虑到此容器的初始化的问题。在此代码下，这行语句执行会出错，因为刚申请的容器元素都为空还没有值没有被初始化，虽然看书上写着内置类型都会初始化成0，但编译是不通过的。我们以后要注意这个问题。