求数列的最大子段和。(教材第4章例15 这里的算法思路与书上不同,复杂度更低。)请编写程序。 算法思路: -2 11 -4 -9 13 -5 7 -3 开局:从左至右扫描。找到第一个正数11,max=11 -2 11 -4 -9 13 -5 7 -3 向右扫描,当前子段和≥0,则将新数-4加入子段。和为7 -2 11 -4 -9 13 -5 7 -3 向右扫描,当前子段和<0,则舍去当前子段(11 -4 -9),继续向右找到第一个正数13。当前max=11<13,则刷新max=13 -2 11 -4 -9 13 -5 7 -3 向右扫描,当前子段和≥0,则将新数-5加入子段(13 -5)。和为8 -2 11 -4 -9 13 -5 7 -3 向右扫描,当前子段和≥0 ,和为15>max。则刷新max=15 -2 11 -4 -9 13 -5 7 -3 向右扫描,当前子段和≥0 ,和为12<max 最终输出max=15 的c代码
时间: 2023-06-13 10:07:51 浏览: 46
```
#include <stdio.h>
int maxSubArray(int arr[], int n){
int max = arr[0]; // 初始最大值为第一个数
int sum = 0; // 当前子段和
for(int i = 0; i < n; i++){
if(sum >= 0){
sum += arr[i]; // 将新数加入子段
}else{
sum = arr[i]; // 舍去当前子段,从当前数开始新的子段
}
if(sum > max){ // 如果当前子段和大于最大值,则更新最大值
max = sum;
}
}
return max;
}
int main(){
int arr[] = {-2, 11, -4, -9, 13, -5, 7, -3};
int n = sizeof(arr) / sizeof(arr[0]);
int result = maxSubArray(arr, n);
printf("最大子段和为:%d\n", result);
return 0;
}
```
相关问题
C语言分别编写出斐波那契数列的递归和非递归算法并分别求时间和空间复杂度
递归算法:
```c
int fibonacci_recursive(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2);
}
}
```
时间复杂度:O(2^n),空间复杂度:O(n)
非递归算法:
```c
int fibonacci_nonrecursive(int n) {
if (n <= 1) {
return n;
} else {
int prev = 0, curr = 1, result;
for (int i = 2; i <= n; i++) {
result = prev + curr;
prev = curr;
curr = result;
}
return result;
}
}
```
时间复杂度:O(n),空间复杂度:O(1)
用Java编写最长上升子序列的算法设计思路和分析其时间复杂度
好的,您的问题是如何用Java编写最长上升子序列的算法设计思路和时间复杂度分析。
最长上升子序列是指一个数列中的最长的严格递增子序列,其长度被称为该数列的最长上升子序列长度。下面给出一种基于动态规划思想的算法设计思路:
1. 定义一个数组dp[length],其中dp[i]表示以第i个元素结尾的最长上升子序列的长度。
2. 初始化dp数组:dp[0] = 1。
3. 遍历整个数列,对于每个位置i,考虑该位置前面的所有元素j,如果j小于i,那么就可以构成一个新的上升子序列:dp[i] = max(dp[i], dp[j]+1)。
4. 遍历完整个数组后,最终dp数组中的最大值就是该数列的最长上升子序列长度。
该算法的时间复杂度为O(n^2),其中n为数列的长度。如果使用优化的数据结构,如二叉查找树等,可以进一步降低时间复杂度,使其达到O(nlogn)。
需要注意的是,上述算法只能求得最长上升子序列的长度,如果需要输出具体的子序列,则需要修改算法,具体实现可以参考其他资料。
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)