C语言——算法-分治问题求解

谁借莪１个温暖的怀抱￠ 2022-12-13 01:48 157阅读 0赞

## 题目描述 ##

给定一个数组arr，返回子数组的最大累加和

例如，arr = \[1, -2, 3, 5, -2, 6, -1\]，所有子数组中，\[3, 5, -2, 6\]可以累加出最大的和12，所以返回12.

\[要求\]

时间复杂度为O(n)O(n)O(n)，空间复杂度为O(1)O(1)O(1)

## 输入 ##

[1, -2, 3, 5, -2, 6, -1]

## 输出 ##

## 备注: ##

> 思路：分治思想或者规划的思想：对一个复杂问题的求解转化为分步骤求解。
> 
> 对原数组从第二个元素左至右遍历，如果当前下标为**i**的元素的值小于当前元素+前一个相邻的元素，更新当前期元素的值=当前元素+前一个相邻的元素，表示截至下标i时，当前得到的子数组最大累加和。
> 
> 一定要判断最后一个元素正负，不能直接用前一个元素+当前元素来更新
> 
> 举例：
> 
> <table style="width:275.43pt;"> 
> <tbody> 
> <tr> 
> <td style="vertical-align:middle;width:77.4pt;">遍历数组下标</td> 
> <td style="vertical-align:middle;width:198pt;">累加和数组</td> 
> </tr> 
> <tr> 
> <td style="vertical-align:middle;">1</td> 
> <td style="vertical-align:middle;">[1,-1]</td> 
> </tr> 
> <tr> 
> <td style="vertical-align:middle;">2</td> 
> <td style="vertical-align:middle;">[1,-1,3]</td> 
> </tr> 
> <tr> 
> <td style="vertical-align:middle;">3</td> 
> <td style="vertical-align:middle;">[1,-1,3,8]</td> 
> </tr> 
> <tr> 
> <td style="vertical-align:middle;">4</td> 
> <td style="vertical-align:middle;">[1,-1,3,8,6]</td> 
> </tr> 
> <tr> 
> <td style="vertical-align:middle;">5</td> 
> <td style="vertical-align:middle;">[1,-1,3,8,6,12]</td> 
> </tr> 
> <tr> 
> <td style="vertical-align:middle;">&nbsp;</td> 
> <td style="vertical-align:middle;">&nbsp;</td> 
> </tr> 
> <tr> 
> <td style="vertical-align:middle;">最后一个元素为</td> 
> <td style="vertical-align:middle;">-1</td> 
> </tr> 
> <tr> 
> <td style="vertical-align:middle;">所以输出</td> 
> <td style="vertical-align:middle;">12</td> 
> </tr> 
> </tbody> 
> </table>

/**
 * max sum of the subarray
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @return int整型
 */
 int maxsumofSubarray(int* arr, int arrLen ) {
 // write code here
 for(int i=1;i<arrLen-1;i++)
 {
 if(arr[i]+arr[i-1]>arr[i])
 {
 arr[i]=arr[i]+arr[i-1];//更新每个下标的数组最大和
 }
 }
 int max;
 if(arr[arrLen-1]>0)//如果最后一个元素大于0
 max=arr[arrLen-1]+arr[arrLen-2];//更新最后一个元素的数组最大和 
 else 
 max=arr[arrLen-2];//舍弃最后一个元素，使用前一个元素的数组最大和
 return max;
 }