در یک گراف وزن‌دار که راس‌ها و یال‌ها وزن دارند، وزن یال‌ها مثبت است ولی راس‌ها می‌توانند وزن منفی نیز داشته باشند. وزن یک زیرگراف القایی از این گراف برابر با جمع وزن راس‌ها و یالهای این زیرگراف می‌باشد. می‌خواهیم تعدادی راس از این گراف را طوری انتخاب کنیم که زیرگراف القایی آن‌ها بیش‌ترین وزن ممکن را داشته باشد.
در خروجی یک عدد صحیح که بیان‌گر بیش‌ترین مقدار وزن یک زیرگراف القایی است را بنویسید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 4 5 1 -5 -1 -1 1 2 1 2 3 1 2 4 1 1 4 6 3 1 5 | 10 |