求子数组最大和的实例代码_C 语言

题目:
输入一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,
因此输出为该子数组的和18。

找到状态转移方程,dp[i]表示前i个数中,包含i的子数组的最大和。要么第i个数自己最大,要么他要和包含i-1的子数组最大和(即dp[i-1])联合在一起.
即dp[i] = max{arr[i],dp[i-1]+arr[i]};

代码如下;

复制代码 代码如下:

#include <stdio.h>
#define max(a,b) (a)>(b)?(a):(b)

int res(int* arr, int len){
    //学到一个定义最小数的方法:)
    int max = -(1<<31);
    int i;
    for(i=1;i<len;i++){
        arr[i] = max(arr[i],arr[i-1]+arr[i]);
        if(max < arr[i]) max = arr[i];
    }
    return max;
}

int main(){
    int arr[] = {1,-2,3,10,-4,7,2,-5};
    printf("%d\n",res(arr,8));
    return 0;
}

时间: 2024-09-18 08:58:09

求子数组最大和的实例代码_C 语言的相关文章

求子数组最大和的解决方法详解_C 语言

题目:输入一个整形数组,数组里有正数也有负数.数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和.求所有子数组的和的最大值.要求时间复杂度为O(n). 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18.如果不考虑时间复杂度,我们可以枚举出所有子数组并求出他们的和.不过非常遗憾的是,由于长度为n的数组有O(n2)个子数组:而且求一个长度为n的数组的和的时间复杂度为O(n).因此这种思路的时间

C 语言插入排序算法及实例代码_C 语言

插入排序是排序算法的一种,它不改变原有的序列(数组),而是创建一个新的序列,在新序列上进行操作. 这里以从小到大排序为例进行讲解. 基本思想及举例说明 插入排序的基本思想是,将元素逐个添加到已经排序好的数组中去,同时要求,插入的元素必须在正确的位置,这样原来排序好的数组是仍然有序的. 在实际使用中,通常是排序整个无序数组,所以把这个无序数组分为两部分排序好的子数组和待插入的元素.第一轮时,将第一个元素作为排序好的子数组,插入第二个元素:第二轮,将前两个元素作为排序好的数组,插入第三个元素.以此类

C语言 奇偶排序算法详解及实例代码_C 语言

C语言奇偶排序算法 奇偶排序,或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算.这是与冒泡排序特点类似的一种比较排序.该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换.下一步重复该操作,但针对所有的(偶-奇)位置数字对.如此交替进行下去. 使用奇偶排序法对一列随机数字进行排序的过程 处理器数组的排序 在并行计算排序中,每个处理器对应处理一个值,并仅有与左右邻居的本地互连.所有处理器可同时与邻居进行比较.交

C 语言快速排序实例代码_C 语言

快速排序是对冒泡法排序的一种改进. 快速排序算法 的基本思想是:将所要进行排序的数分为左右两个部分,其中一部分的所有数据都比另外一 部分的数据小,然后将所分得的两部分数据进行同样的划分,重复执行以上的划分操作,直 到所有要进行排序的数据变为有序为止. 可能仅根据基本思想对快速排序的认识并不深,接下来以对n个无序数列A[0], A[1]-, A[n-1]采用快速排序方法进行升序排列为例进行讲解. (1)定义两个变量low和high,将low.high分别设置为要进行排序的序列的起始元素和最后一个元

C++ string 字符串查找匹配实例代码_C 语言

在写C++程序中,总会遇到要从一个字符串中查找一小段子字符串的情况,对于在C中,我们经常用到strstr()或者strchr()这两种方法.而对于C++的string,我们往往会用到find(). C++:#inlcude<string> C: #include<string.h> find():在一个字符串中查找一个指定的单个字符或字符数组.如果找到,就返回首次匹配的开始位置:如果没有查找到匹配的内容,就返回string::npos. find_first_of():在一个目标串

VC++简单实现关机、重启计算机实例代码_C 语言

本文以一个实例形式介绍了VC++简单实现关机.重启计算机的方法,代码比较实用,有一定的参考价值.完整实例代码如下: void CWebBrowserView::OnMenuShutdown() { // TODO: 在此添加命令处理程序代码 if (AfxMessageBox("确定要关机吗?",MB_YESNO) == IDYES) { HANDLE hToken; TOKEN_PRIVILEGES tkp; // Get a token for this process. if (

C语言之实现控制台光标随意移动的实例代码_C 语言

原理引入windows.h,首先是要获得输入的东西,然后通过判断: 1.方向键:执行上下左右的移动功能 2 .回车键:执行换行的功能. 3.普通键:输入功能. 终点就是要获取到屏幕上的坐标,当按下了方向键以后,坐标值+1,或者减一,从而实现了光标的自由移动. //C语言实现控制台中光标随意移动 #include <stdio.h> #include <windows.h> #include <conio.h> HANDLE hout; //获得输入 char getIn

使用C++的string实现高精度加法运算的实例代码_C 语言

对于超大数字的运算,用long long int仍然不能解决,这时候就需要考虑通过模拟运算和数组存储来实现高精度运算. 本文讨论借助C++的string来实现高精度的运算. 首先输入的量直接存储为string,设为s1和s2. 接下来设计一个反转函数,用于把整个字符串反转(为了方便后续计算). string reverseStr(string input){ string output = ""; for(int i = 0; i < input.length(); i++){

C++ 继承详解及实例代码_C 语言

C++继承可以是单一继承或多重继承,每一个继承连接可以是public,protected,private也可以是virtual或non-virtual.然后是各个成员函数选项可以是virtual或non-virtual或pure virtual.本文仅仅作出一些关键点的验证. public继承,例如下: 1 class base 2 {...} 3 class derived:public base 4 {...} 如果这样写,编译器会理解成类型为derived的对象同时也是类型为base的对象