Max Sum of Subsequence
Submit solution
Points:100
(partial)
Time limit:0.5s
Memory limit:32M
Author:
Tags
Arrays
Difficulty
Easy
Write a program that finds the maximal sum of consecutive elements in a given array of N numbers.
- _Can you do it with only one loop (with single scan through the elements of the array)?_
Input
- On the first line you will receive the number N
- On the next N lines the numbers of the array will be given
Output
- Print the maximal sum of consecutive numbers
Constraints
- 1 <= N <= 1024
Sample tests
| Input | Output |
|---|---|
| 10 2 3 -6 -1 2 -1 6 4 -8 8 |
11 |
Comments
Ох, Дончо, Дончооо...
Привет, Това ще помогне: Kadane's algorithm https://medium.com/@rsinghal757/kadanes-algorithm-dynamic-programming-how-and-why-does-it-work-3fd8849ed73d
Моля някой да обясни как 2, -1, 6, 4 са последователни елементи?
Наистина е tricky... но понеже никъде не се казва Increasing Sequence / Decreasing Sequence / Sequence of Equals -т.е. не е специфирано каква е последователността на елементите (нарастваща, намаляваща или са еднакви един след друг) - просто имаме каквито и да са последователни елементи, т.е. позициите им се движат i, i+1, i +2....
Също така, винаги можеш да си погледнеш Sample Input за разяснение - там ясно се вижда какво се има предвид :)
Здравейте,
Аз също имам нужда от разяснение на условието - как разбираме кои елементи са последователни ? Благодаря предварително !
Последователни са елементите които са един след друг в масива :)
Иначе условието може да се перефразира и така - кой подмасив от дадения масив има максимална сума. Пример за подмасиви:
2
2 3
2 3 -6 ..
3 -6 -1
и т.н.
Едит : 10 е броя елементи :)
Защо от сорс кода на Java получавам 15? (Тук не мога да си публикувам кода!)
Може ли за малко помощ,защото изобщо не мога да схвана къде ми е грешката: Аз разбирам по следния начин условието: Вход 10 2 3 -6 -1 2 -1 6 4 -8 8 => редиците са (2<3>-6<-1) (2>-1<6>4) (-8<8) => най-голямата сума = 11 Тоест, редицата започва независимо дали първото число в нея е по-голямо или по-малко от следващото, идеята е да се редуват, докато няма два еднакви последователни знака.
UPDATE Сега стигнах до извода, че задачата няма нищо общо с първоначалните ми разбирания - няма никакви сравнения между съседните елементи.
Здравей, няма определен брой елементи за да се получи максималната сума :) Тоест може да са всички елементи ако са положителни :) моето решение е с 2 цикала (за проверката на максималната сума)
Защо в условието има долни черти? _Can you do it with only one loop (with single scan through the elements of the array)?_
Какво значи consecutive elements ?
Има гоогле преводач :) иначе значи последователни елементи :) Както са показани в примера (болднатите елементи)
-