《剑指Offer——连续子数组的最大和,礼物的最大价值》代码

• 前言
• 一、示例
• • 1.连续子数组的最大和
  • 2.礼物的最大价值
• 二、代码解析
• • 1.新建.cpp文件
  • • 代码如下（示例）：
• 三，测试

//==================================================================
// 《剑指Offer——连续子数组的最大和,礼物的最大价值》代码
// 题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整
// 数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
// 题目：在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值
// （价值大于0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向左或
// 者向下移动一格直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计
// 算你最多能拿到多少价值的礼物？
//==================================================================

//==================================================================
// 《剑指Offer——连续子数组的最大和,礼物的最大价值》代码
// 题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整
// 数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
// 题目：在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值
// （价值大于0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向左或
// 者向下移动一格直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计
// 算你最多能拿到多少价值的礼物？
//==================================================================



#include 
#include
#include
using namespace std;


int maxSubArray(vector& nums)
{
	if (nums.empty() || nums.size() <= 0)
	{
		return 0;
	}

	int len = nums.size();
	int nCurSum = 0;
	int nGreatestSum = 0x80000000;
	for (int i = 0; i < len; ++i)
	{
		if (nCurSum <= 0)
		{
			nCurSum = nums[i];
		}
		else
		{
			nCurSum += nums[i];
		}

		if (nCurSum > nGreatestSum)
		{
			nGreatestSum = nCurSum;
		}
	}

	return nGreatestSum;
}




int maxValue1(vector>& grid)
{
	if (grid.empty() || grid.size() <= 0 || grid[0].size() <= 0)
	{
		return 0;
	}
	int row = grid.size();
	int columns = grid[0].size();

	vector> dp(row + 1, vector(columns + 1, 0));
	for (int i = 1; i <= row; ++i)
	{
		for (int j = 1; j <= columns; ++j)
		{
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
		}
	}

	return dp[row][columns];
}


int maxValue2(vector>& grid)
{
	if (grid.empty() || grid.size() <= 0 || grid[0].size() <= 0)
	{
		return 0;
	}
	int row = grid.size();
	int columns = grid[0].size();

	vector arr(columns, 0);
	for (int i = 0; i < row; ++i)
	{
		for (int j = 0; j < columns; ++j)
		{
			int left = 0;
			int up = 0;

			if (i > 0)
				up = arr[j];

			if (j > 0)
				left = arr[j - 1];

			arr[j] = max(left, up) + grid[i][j];
		}
	}

	int maxValue = arr[columns - 1];


	return maxValue;
}

int main()
{
	vector nums = { -2,1,-3,4,-1,2,1,-5,4 };
	cout << "连续子数组的最大和--->" << maxSubArray(nums) << endl << endl;

	vector> grid =
	{
		{1,3,1},
		{1,5,1},
		{4,2,1}
	};
	cout << "礼物的最大价值--->二维数组---->" << maxValue1(grid) << endl << endl;
	cout << "礼物的最大价值--->一维数组---->" << maxValue2(grid) << endl << endl;
	return 0;
}