Program to find the largest sum of contiguous integers in
the array. O(n)
Answer Posted / jjaspirin
I came to this website looking for the solution and finally
ended up writing it myself. Hope this is useful for someone
else.
Here is a working solution. Set the array "a" and N_ELEMENTS
accordingly. Some cases are not covered but should be an
easy fix.
#include <stdio.h>
#define N_ELEMENTS 7
int main() {
int a[N_ELEMENTS] = {-1, 2, -3, 2, 0, 5, -11 }; // if
you change the array, make sure you change N_ELEMENTS
int i = 0;
while(a[i] < 0 && i<N_ELEMENTS) {
i++;
}
if (a[i] < 0) {
printf ("DEBUG: array with only negative numbers.
Print the smallest negative number as the sum and we are
done.\n");
}
int sum_p=0, sum_n = 0;
int largest_sum = 0;
while (i<N_ELEMENTS) {
if (a[i] > 0) {
sum_p += a[i];
}
else {
sum_n += a[i];
}
if (sum_p+sum_n > largest_sum) {
largest_sum = sum_p + sum_n;
}
if (sum_p+sum_n <= 0) {
// find the next positive number
while(a[i] < 0 && i<N_ELEMENTS) {
i++;
}
if (a[i] < 0 || i == N_ELEMENTS) {
break;
}
sum_p = 0;
sum_n = 0;
} else {
i++;
}
}
printf ("DEBUG: The largest consecutive sum = %d\n",
largest_sum);
}
Is This Answer Correct ? | 3 Yes | 2 No |
Post New Answer View All Answers
write a function to give demostrate the functionality of 3d in 1d. function prototye: change(int value,int indexX,int indexY,int indexZ, int [] 1dArray); value=what is the date; indexX=x-asix indexY=y-axis indexZ=z-axis and 1dArray=in which and where the value is stored??
how to create a 3x3 two dimensional array that will give you the sums on the left and bottom columns
What is full form of PEPSI
write a c program to input initial & final time in the format hh:mm and find the time intervel between them? Ex inputs are initial 06:30 final 00:05 and 23:22 final 22.30
How can you relate the function with the structure? Explain with an appropriate example.
Write a routine to implement the polymarker function
What is the difference between proc means and proc tabulate ? explain with a simple example when you have to use means or tabulate?
why nlogn is the lower limit of any sort algorithm?
how to test pierrot divisor
What is data _null_? ,Explain with code when u need to use it in data step programming ?
How to palindrom string in c language?
can you use proc sql to manpulate a data set or would u prefer to use proc report ? if so why ? make up an example and explain in detail
Cluster head selection in Wireless Sensor Network using C programming language.
Develop a routine to reflect an object about an arbitrarily selected plane
Write a program to model an exploding firecracker in the xy plane using a particle system