自旋在单线程上的应用
【申明:本文仅限于自我归纳总结和相互交流,有纰漏还望各位指出。 联系邮箱:[email protected]】
题目:输入一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
题目分析:
一、如果数组中全部为负数,则返回最大负数值即可
二、当既有正数也有负数的时候:
(1)从左往右叠加,如果当前叠加值小于或者等于0,则放弃,叠加总和清0(加一个负数或者0是毫无意义的),从此位置继续重新叠加
(2)如果当叠加总和大于上一次记录的叠加总和,则更新叠加总和即可
算法实现:
#include <stdio.h> int return_sub_max(int *array, int size) { int max_sum = 0, temp = 0; int max = array[0]; int i = 0; for(;i<size; i++) { temp += array[i]; if(temp <= 0) { temp = 0; continue; } /*record max total*/ if(temp > max_sum) { max_sum = temp; } /*record max value if all value are negative*/ if( array[i] > max) { max = array[i]; } } return (max_sum == 0? max:max_sum); } int main() { //int array[] = {-1, -2, -3, -10, -4, -7, -2, -5}; //int array[] = {1, -2, 3, 10, -4, 7, 2, -5}; int array[] = {1, 2, 3, 10, 4, 7, 2, 5}; printf("max = %d\n", return_sub_max(&array[0], 7)); return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。